retagged by
2,196 views

1 Answer

Best answer
6 votes
6 votes

Given Language is L$= \left \{ a^{i}b^{j}c^{k}d^{l} | i=k\ or\ j=l \right \}$

For Simplicity we can consider it as

L=$= \left \{ a^{k}b^{j}c^{k}d^{l} \right \}\cup \left \{ a^{i}b^{l}c^{k}d^{l} \right \}$

So the given language is Either n number of a's followed by n number of c's or n number of b's followed by n number of d's.

The machine which will accept the above language will be nondeterministic pushdown automata (NPDA).

Hence the given language is Context free language (CFL).

And another language is L=$\left \{ a^{m}b^{n}c^{m}d^{n} \right \}$ which is not context free language.

It can,t be accepted by NPDA.First you have push all a's then push all b's .Now a's has to match with c's but top of stack is b's.

Machine will stuck at that time since there is no way to match a's with c's and b's with d's.

So it can,t be accepted by NPDA .Given Language is Context Sensitive(CSL).

selected by

Related questions

2 votes
2 votes
1 answer
2
Anjana Babu asked Nov 24, 2016
1,710 views
Please Explain why the following is accpeted/rejected by PDA . ( Need detail explanation )S1 = { 0n 0m 1n 0m | n,m>0 }S2 = { 0n 0m 1n 1m 0m | n,m>0 }S3 = { am 0m 1n...
1 votes
1 votes
2 answers
3
shekhar chauhan asked Jun 6, 2016
927 views
If a given CFL Language is L= {a^n b^n ;n>=0} then how can we determine the value of L^2 .Explain with an example .