The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+2 votes
how to determine that this is not in DCFL and also for the odd length palindrome language as well,
asked in Theory of Computation by (145 points)
retagged by | 86 views

2 Answers

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.

answered by (269 points)
0 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^,here,actually in palindrome(even),at center the symbols should be same( 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,...
answered by (27 points)

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

28,981 questions
36,818 answers
34,706 users