Question

Consider language L=0i1ʲ0ᵏ .

Is L regular? If yes: give a DFA in form of a state diagram. If not: prove, using the pumping lemma for regular languages, that L is not regular.

Answer 1

The language L is not regular and can be proven using the pumping lemma for regular languages.

Step-by-step explanation:

The language L = i = 2; j = k+1; k ≥ 0 is not regular. We can prove this using the pumping lemma for regular languages.

Let's assume that L is regular and can be recognized by a deterministic finite automaton (DFA). Let the number of states in that DFA be n.

Consider the string w = 0n+11n+20n+3. According to the pumping lemma, we can write w as xyz, where:

x = 0p

y = 0q

z = 0r1s0t

|y| ≥ 1

|xy| ≤ n

Now, when we pump y, we can repeat it any number of times to obtain a new string, say u. Since |xy| ≤ n, pumping y does not change the number of 0's before the 1. Therefore, the resulting string u will not be in L, as the number of 0's before the 1 will no longer be one more than the number of 1's after the 1. This contradicts the definition of L.

Hence, we can conclude that L is not regular.