380 views
1 votes
1 votes
L2={a^i b^(i^2) } where I is natural no.
Identify the class of language and it's complement...

1 Answer

0 votes
0 votes
L2 is clearly not CFL because we cannot compute square values using just the stack logic. Think of it as a cyclic dependency; we need to know the number of ‘a’ present in the input to be able to select appropriate numbers of ‘a’ we must push in our stack. But to know the number of ‘a’ we must push into stack. So it is certainly not possible.

For its complement, there will be one case as follows: (i am not 100% sure of this logic)

“starting with a and ending with b but |b| != $|a|^{2}$” .This case will again make it non-CFL but CSL.

Related questions

2 votes
2 votes
1 answer
1
VS asked Jan 24, 2018
544 views
L={ xy | x,y$\epsilon$ (a+b)*, na(x) = nb(y) }
5 votes
5 votes
0 answers
2
Himanshu1 asked Oct 31, 2015
558 views
L = {anbm | n mod m = 0 , n>=0 , m>0} Given language isA) CFLB) CSLC) DCFLD) RECE) RE
1 votes
1 votes
3 answers
3
Shefali asked Oct 24, 2015
739 views
$L=\left\{ w\in(a+b)^* \mid w \\ \text{ has at least as many occurrences of (bba)'s as (abb)'s}\right\}$    Identify the class of the language.
0 votes
0 votes
1 answer
4
admin asked Sep 23, 2015
1,285 views
Identify the class of the language $L = \Bigl \{a^n b^m \mid n \leq m \leq 2n\Bigr \}$.a) CFL but not DCFLb) DCFL but not regularc) not CFL