870 views
0 votes
0 votes
Construct a PDA for set of strings over {a,b,c,d} such that

L={ a^i b^j c^k d^l / i=k or j=l , i,j,k,l >=1}

2 Answers

0 votes
0 votes

 

This a NCFL.

L={ a^i b^j c^k d^l / i=k or j=l , i,j,k,l >=1} Then This Language can be written like this

L = {a^i b^j c^i d^l  ∪  a^i b^j c^k d^j  } Here

L1 =   {a^i b^j c^i d^l}

L2 = { a^i b^j c^k d^j }

Then PDA  Will be 

0 votes
0 votes
We can construct a PDA for this one like- 1 pda which compares a's and c's and another one for b's and d's and Union them(or) so its acceptable by NDCFL

Another possibility- If we put condition like i=k AND j=l then at the same time we can't compare both so this one is not CFL and NDPDA or DPDA for this

Related questions

0 votes
0 votes
1 answer
2
Abhisek Tiwari 4 asked Nov 6, 2018
703 views
Consider Ldf set all languages accepted by DPDA by final state,Lef set of all languages accepted by DPDA by Empty stack ThenA)Ldf proper subset of Lef.B)Ldf = Lef.C)Lef ...
0 votes
0 votes
0 answers
4
Na462 asked Sep 9, 2018
606 views
Consider following PDA WHICH OF FOLLOWING IS TRUE ABOUT LANGUAGE ACCEPTED BY IT ?A. Regular but infiniteB. Regular but finiteC. DCFL but not regularD. CFL but not DCFL