The Gateway to Computer Science Excellence
+4 votes
538 views
1. L ={ a^n b^m c^x d^y | n=m or x=y}

2. L ={ a^n b^x c^m d^y | n=m or x=y}

Classify above in CFL/DCFL?
in Theory of Computation by Boss (25.6k points)
retagged by | 538 views
0
1) DCFL

2) not CFL
0
Why second is not CFL?
+2
Because when we start pushing "a" {for matching with the number of "c"} into the stack then after that when we start pushing "b"{for matching with the number of "d"} into the stack. and when the "c" begin we don't have our top of the stack pointing to "a"{for popping the "a" as no of push operation of "a" due to "occurrence a" = no of pop operation of "a" due to "occurrence of c"}, because it is now pointing to "b".

That's why 2 is not CFL.
0

But we have or operation.Cant we handle in non deterministic manner?We have choice here ,first we can see first condition.If that fails then we can see second condition.?NPDA can create multiple copies??

+1

2 is CFL not DCFL.

we first push for a then do nothing for b and then pop for c. if stack empty then it is CFL else not.

                                                                            OR

  we do nothing for a then push for b then do nothing for c and then pop for d. if stack empty then it is CFL else not.

2 Answers

+5 votes
Best answer
1. L ={ a^n b^m c^x d^y | n=m or x=y} CFL but not DCFL

PDA have to copies ::
COPY 1: push a's , pop b's ---> in end stack empty , c ->ignore , d->ignore

COPY 2: a->ignore , b->ignore,push c's , pop d's ---> in end stack empty

2. L ={ a^n b^x c^m d^y | n=m or x=y} CFL but not DCFL

PDA have to copies ::
COPY 1: push a's , b ->ignore ,pop c's ---> in end stack empty , d->ignore

COPY 2: a->ignore , push b's, c->ignore,pop d's ---> in end stack empty,
by Boss (10.8k points)
selected by
0
This is absolutely correct.I was suggesting the same above,but was not getting close
0
1. Why 1 can't be DCFL?
0
SO 1ST ONE IS NOT DCFL DUE TO TWO CHOICES AT A POINT ???
0
Best explanation
0
1st is DCFL
0

L ={ a^n b^m c^x d^y | n=m or x=y} CFL but not DCFL

instead of this
COPY 1: push a's , pop b's ---> in end stack empty , c ->ignore , d->ignore

can we do this???

push a's , pop b's ---> in end stack empty , c ->push c's , d->pop d's ---->in end stack is empty accept it?

 

0 votes
in pda alternate comparison is not possible so L2is not CFL
by Active (3.6k points)
0
But why NPDA cant do this?
0
Alternate comparison is not required as there is "or" not "and" given..

Related questions

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
50,737 questions
57,292 answers
198,236 comments
104,919 users