The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+4 votes

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

asked in Theory of Computation by Junior (679 points) | 105 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 (28.7k points)
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

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

29,156 questions
36,980 answers
34,822 users