TOC DCFL vs CFL

Question

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?

Comments

1) DCFL

2) not CFL

---

Why second is not CFL?

---

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.

---

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

---

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.

Answer 1

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,

Comments

This is absolutely correct.I was suggesting the same above,but was not getting close

---

1. Why 1 can't be DCFL?

---

SO 1ST ONE IS NOT DCFL DUE TO TWO CHOICES AT A POINT ???

---

Best explanation

---

1st is DCFL

---

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?

 

Answer 2

in pda alternate comparison is not possible so L2is not CFL

Comments

But why NPDA cant do this?

---

Alternate comparison is not required as there is "or" not "and" given..