in Theory of Computation retagged by
2,201 views
0 votes
0 votes

What does this Language Represents ? And what is the machine which is able to represent this Language.

L = { a^i b^j c^k d^l }  where i = k or j = l

How it is different from  L = {a^m b^n c^m d^n}

in Theory of Computation retagged by
2.2k views

1 Answer

6 votes
6 votes
Best answer

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

4 Comments

Hi MK does your simplified lang in your ans represents the same lang which is given in question ?
0
0
off course bro .That is comparison with "or (U)" .

You tell me where is confusion Now.
0
0
I got it .one more thing i need to ask the lang which i have written in my question is CFL OR DCFL ? first lang in which i used i and j .
0
0