search
Log In
5 votes
939 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
retagged by
939 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

7 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,

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
0
But why NPDA cant do this?
0
Alternate comparison is not required as there is "or" not "and" given..

Related questions

1 vote
3 answers
1
1 vote
0 answers
2
513 views
Given that: { A^m B^n C^k/ if (k=even) then m=n} { A^m B^n C^k/ if (n=even) then m=k} Which of the above languages are DCFL? According to me it is CFL as we have to first count k and then compare other inputs.. same for second language but ... given is both are DCFL? it is only possible if skip path is exists here? does it exist for DCFLs? so confused please guide me? if given answer is correct?
asked Jan 3, 2019 in Theory of Computation S Ram 513 views
3 votes
2 answers
3
500 views
Let A is the language where no of 'a' is greater than no of 'b' and B is the language where no of 'b' is greater than no of ‘a’ the language A.B is ______________ a. Regular b. DCFL but not Regular c. CFL but not DCFL d. REC but not DCFL
asked Jan 27, 2018 in Theory of Computation Tuhin Dutta 500 views
0 votes
2 answers
4
621 views
Isn't WxWr DCFL as X acts as marker so DCFL should be right choice , why is it categorized as CFL and not DCFL?
asked Dec 2, 2016 in Theory of Computation vishal8492 621 views
...