retagged by
597 views

2 Answers

4 votes
4 votes

We can write complement of L as follows...

L'= {a^m b^n a^p | m!=n or m!=p or n!=p }

Which can be accepted by NPDA ...even given language is CSL...

To accept a^n b^n c^n , you need to make sure that three numbers are equal. To accept a*b*c*∖a^n b^n c^n, you just need to make sure that you're in one of the following three cases:

  1. The number of a's is different from the number of b's; or
  2. The number of a's is different from the number of c's; or
  3. The number of b's is different from the number of c's.

Write a PDA for each of these cases, then combine them by jumping nondeterministically to each one from the start state.

http://cs.stackexchange.com/questions/7190/construct-a-pda-for-the-complement-of-anbncn?noredirect=1&lq=1

edited by
2 votes
2 votes

L={ a n b n a n | n>=1} is a context sensitive language. Such strings are accepted by linear bonded automata

compliment of any  CSL is also a CSL.

Hence  compliment of L={ a n b n an | n>=1} is a context sensitive language.

CSL is TYPE 1

edited by

Related questions

0 votes
0 votes
0 answers
1
Manu Thakur asked Sep 29, 2017
573 views
Is the following language CFL?L = complement of {$a^ib^jc^k$ | i!=j and j!=k}
0 votes
0 votes
1 answer
3
Shahid asked Oct 31, 2014
1,416 views
0 votes
0 votes
0 answers
4
hacker16 asked Dec 18, 2017
695 views
Let Ʃ = {a, b} and L = {anwan | n ≥ 1, w ∈ Ʃ*}.ThenL is context free but not regularL is not context free but regularL is context free as well as regularL is neithe...