Question

LB = {w|w e {a,b,c}^*, w =c^kbba^n, n<k}.

1. Is LB regular or not?

2. Give proof that supports your answer.

Answer 1

LB = { w | W { a,b,c } , W= , n<k }

1.

This Language is not regular.

2.

proof : -

For any regular language, there exists a Finite Automata ( NFA or DFA ). Finite Automata has limited memory. comparisons are not possible in Finite Automata .

you can clearly see the comparison " n<k " in the Language defenition. comparison always requires memory. So Drawing Finte Automata (DFA or NFA ) is impossible . This Language s not Regular because there are no Finite Automata Representing This Language .

--------------------------------------------------------------

note :- provng the language is not regular using pumping lemma is not possible because " k " will be always greater than " n" . so for any given pumping length p . The language always Satisifie pumping lemma.