GATE CSE
First time here? Checkout the FAQ!
x
+1 vote
61 views
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 (123 points)   | 61 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 (87 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^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,...
answered by (11 points)  


Top Users Sep 2017
  1. Habibkhan

    7828 Points

  2. Warrior

    2746 Points

  3. rishu_darkshadow

    2692 Points

  4. Arjun

    2672 Points

  5. A_i_$_h

    2426 Points

  6. nikunj

    1980 Points

  7. manu00x

    1920 Points

  8. Bikram

    1854 Points

  9. makhdoom ghaya

    1770 Points

  10. SiddharthMahapatra

    1718 Points


26,239 questions
33,805 answers
80,214 comments
31,159 users