Question

Determine whether or not the following languages are regular. If the language is regular then give an NFA or regular expression for the language. Otherwise, use the pumping lemma for regular languages or closure properties to prove the language is not regular.

1) L = { 0 n1 k : k ≤ n ≤ 2k}

2) L = { 0 n1 k : n > 0, k > 0 } È { 1 k0 n : k > 0, n > 0}

Answer 1

(1) L = { 0 ⁿ 1 ^k : k ≤ n ≤ 2k}

Finite automata is not having memory element so FA can not Perform any comparison so above languagr is not Regular laguage because comparison is envolved.

(2) L = { 0 ⁿ1 ^k : n > 0, k > 0 } È { 1 ^k0 ⁿ : k > 0, n > 0} // here meaning of E' is not given

Regular Expression for { 0 ⁿ1 ^k : n > 0, k > 0 } is 0⁺ 1⁺

Regular Expression for { 1 ^k0 ⁿ : k > 0, n > 0} is 1⁺ 0⁺

so operation between this is also regular hence its Regular

Note: here meaning of E' is not given so we can assume any normal decidable operation