retagged by
1,480 views
3 votes
3 votes
how to determine that this is not in DCFL and also for the odd length palindrome language as well,
retagged by

2 Answers

1 votes
1 votes
that palindrome is of form L=WW^R. so,here if you want to push and pop of stack first you need to find what is the center.
for example,in L=WcW^R,it is obvious that after seeing 'c',you can now pop the stack....but it is not like in the case of WW^R.so,here,actually in palindrome(even),at center the symbols should be same(e.g:aba.aba........here at center i.e.,i put the dot to represent it,....symbols are same....but it need not always the center where two consecutive symbols are same....
so,you should go with NPDA to check this,...
0 votes
0 votes

in easy way we can say that if push and pop are cleare then it is dcfl otherwise cfl.

for example a^nb^n U a^nb^2n in this language there is ambiguity . we can not decide how many a's are pop with single a's or two b's . so it is cfl.

Related questions

2 votes
2 votes
0 answers
1
sunil sarode asked Jan 19, 2018
1,704 views
Consider two languages LA and LB over Σ={a,b}.LA= {a^ib^ja^k | i,j,k ≥ 0 and j=i+k}LB= {b^ia^jb^k | i,j,k ≥ 0 and j=i+k} Then ( LA ∪ LB ) is : A DCFL but not regul...
1 votes
1 votes
1 answer
2
4 votes
4 votes
1 answer
3
1 votes
1 votes
1 answer
4
Himanshu1 asked Nov 2, 2015
991 views
Give an example of Unambiguous CFL which is not DCFL .