retagged by
4,758 views
5 votes
5 votes

Please some one explain. why complement of this language is CFL.

retagged by

2 Answers

Best answer
8 votes
8 votes

$L= \left \{ a^nb^na^n \;|\; n\geq 1\right \}$

Complement of $L$,  will consist of strings as

1. $\left \{ a^ib^ja^k \;|\; i \neq j \;or\;j \neq k \;or k \neq i \right \}$

2. All strings starts with $b$. 

3. $a^*b^*$ or  $b^*a^*$. 

4. All strings contains $bab$ as substring. 

5. May be something left, but regular 

it will be CFL. 

selected by
0 votes
0 votes

Given language is finite.

Finite language == Regular.

Regular languages are closed under complimentation.

Every regular language is also CFL

Related questions

3 votes
3 votes
1 answer
1
8 votes
8 votes
3 answers
3
Payal Rastogi asked Nov 2, 2015
7,119 views
The complement of the language $L$ containing an equal number of $a's$,$b's$ and $c's$ is (a) regular(b) context free(c) context sensitive but not context free(d) recursi...
2 votes
2 votes
0 answers
4