retagged by
3,379 views
5 votes
5 votes
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?
retagged by

2 Answers

Best answer
9 votes
9 votes
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

Related questions

1 votes
1 votes
2 answers
1
1 votes
1 votes
1 answer
2
1 votes
1 votes
2 answers
3
ggwon asked Dec 29, 2022
703 views
L = {$a^{n+m}b^{n}a^{m} | n,m \geq 0$}Is the above language DCFL or CFL ?