1 votes 1 votes What is the type of the compliment of the given language $L=\{a^n b^n a^n \mid n \geq 1 \}$? Theory of Computation context-free-language + – Rock asked Jul 15, 2016 retagged Jul 4, 2017 by Arjun Rock 597 views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
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: The number of a's is different from the number of b's; or The number of a's is different from the number of c's; or 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 papesh answered Jul 15, 2016 edited Jan 8, 2017 by papesh papesh comment Share Follow See all 0 reply Please log in or register to add a comment.
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 sh!va answered Jul 15, 2016 edited Jul 15, 2016 by sh!va sh!va comment Share Follow See all 2 Comments See all 2 2 Comments reply Rock commented Jul 15, 2016 reply Follow Share Please read the question carefully. It's not a^n b^n c^n...It's a^n b^n a^n. If it's a^n b^n c^n then it's very easy. 0 votes 0 votes sh!va commented Jul 15, 2016 reply Follow Share Corrected explanation.. But answer will be same.. Type 1 0 votes 0 votes Please log in or register to add a comment.