GATE CSE
First time here? Checkout the FAQ!
x
0 votes
35 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 (83 points)   | 35 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 (83 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 Jul 2017
  1. Bikram

    4894 Points

  2. manu00x

    2888 Points

  3. Debashish Deka

    1870 Points

  4. joshi_nitish

    1776 Points

  5. Arjun

    1496 Points

  6. Hemant Parihar

    1306 Points

  7. Shubhanshu

    1128 Points

  8. Arnab Bhadra

    1114 Points

  9. pawan kumarln

    1114 Points

  10. Ahwan

    940 Points


24,089 questions
31,062 answers
70,677 comments
29,400 users