2076 7

Theory of Computation20765 marksPumping Lemma

Show that language is not a regular language. L = 0m 1m mid m geq 1

Show that language is not a regular language. $L = { 0^m 1^m \mid m \geq 1 }$ [5]

--- If A is a regular language, then there exists a pumping length p such that any string s with s ≥ p can be divided into three parts s = xyz satisfying: 1. xy^i z ∈ A for every i ≥ 0 2. y 0 (y cannot be empty) 3. xy ≤ p (xy together must not exceed pumping length) --- Step 1: Assume L is regula...

Up nextDescribe the Turing machines with multiple tape, multiple track and storage in state.