GATE CSE
First time here? Checkout the FAQ!
x
+4 votes
82 views

L={anbpcan   ∣p,n>0}∪{anbpdbp   ∣p,n>0}

asked in Theory of Computation by Junior (505 points)   | 82 views
yes it is DCFL.

1 Answer

0 votes
Best answer

Yes it's DCFL.

1. Push all a's and b's
2. if c comes, then ignore this c and pop all the b's
3. when a's come again, pop one 'a' from stack for every input 'a'
4. input is completed and stack contains stack contains stack symbol on TOS, accept the language.

1. Push all a's and b's
2. if d comes, then ignore this d
3. when b's come again, pop one 'b'  from stack for every input 'b'
4. input is completed and stack contains 'a' on the top of the stack, then accept the language

answered by Veteran (11.1k points)  
selected by
Thanks for the explanation. But can we accept this language with DPDA without e-transitions? I can see that in first case we can accept this input because stack becomes empty but in other case stack is not empty.

Please suggest if there is any way to accept the language L without making a e-transition to final state or making e-transition to make the stack empty.

Also, What is general idea to  identify that a DPDA exists(possibly real time DPDA (without e-transitions)) by only seeing the grammar(Since this problem is undecidable). I am asking this from GATE perspective.
what is the problem with epsilon-transitions? We can make a DPDA for this language hence it;s DCFL.
How you pop b"s when c comes ?
But DCFL not closed under union than

How can DCFL

@Nitesh Choudhary

if a class is not closed under some operation, it means atleast one element of that class does not satisfy closer property, it does not mean that every element of that class will not satisfy closer property...

DCFL are not closed under union---> "this means that there exist atleast one language which is DCFL and not closed under union, it does not mean that every language in DCFL are not closed under union(as in above case)"

But we cannot make dpda for this language NPDA is possible with adding both dfa and start edge go based on a in both dfa
I mean if two edge with. a input so that is not dpda

you can make DPDA,

push all a's then all b's, after this if c comes, pop out all the b's and then compare incoming a's with a's present in stack.

                                                     else if d comes, compare incoming b's with b's present in stack

at every step we are deterministic in taking decision.

How u pop out b's when c comes ?? Didn't have push and pop for b's
Okk I got it

Dpda possible for this language

Thanks for explaining and sharing a conceptual question


Top Users Sep 2017
  1. Habibkhan

    6362 Points

  2. Warrior

    2234 Points

  3. Arjun

    2212 Points

  4. nikunj

    1980 Points

  5. manu00x

    1726 Points

  6. SiddharthMahapatra

    1718 Points

  7. Bikram

    1716 Points

  8. makhdoom ghaya

    1660 Points

  9. A_i_$_h

    1552 Points

  10. rishu_darkshadow

    1512 Points


25,991 questions
33,561 answers
79,414 comments
31,029 users