The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+20 votes

Consider the languages

$L1=\{0^i1^j\ \mid i \neq j\}, $

$L2=\{0^i1^j\mid i=j\},$

$L3=\{0^i1^j \mid i=2j+1\},$

$L4=\{0^i1^j \mid i\neq2j\}$

- Only $L2$ is context free.
- Only $L2$ and $L3$ are context free.
- Only $L1$ and $L2$ are context free.
- All are context free

+31 votes

Best answer

All are context free.

$L1 \rightarrow$ Push $0$ on stack and when $1$ comes, start popping. If stack becomes empty and $1$'s are remaining start pushing $1$. At end of string accept if stack is non- empty.

$L2 \rightarrow$ Do the same as for $L1$, but accept if stack is empty at end of string.

$L3 \rightarrow$ Do, the same as for $L2$, but for each $0$, push two $0$'s on stack and start the stack with a $0$.

$L4 \rightarrow$ Do the same as for $L1$, but for each $0$, push two $0$'s on stack

All are in fact DCFL. Pushing two $0$'s on stack might sound non-trivial but we can do this by pushing one symbol and going to a new state. Then on this new state on empty symbol, push one more symbol on stack and come back.

$L1 \rightarrow$ Push $0$ on stack and when $1$ comes, start popping. If stack becomes empty and $1$'s are remaining start pushing $1$. At end of string accept if stack is non- empty.

$L2 \rightarrow$ Do the same as for $L1$, but accept if stack is empty at end of string.

$L3 \rightarrow$ Do, the same as for $L2$, but for each $0$, push two $0$'s on stack and start the stack with a $0$.

$L4 \rightarrow$ Do the same as for $L1$, but for each $0$, push two $0$'s on stack

All are in fact DCFL. Pushing two $0$'s on stack might sound non-trivial but we can do this by pushing one symbol and going to a new state. Then on this new state on empty symbol, push one more symbol on stack and come back.

0

Hi @Arjun sir , in case of L_{1 }={0^{i }1^{j }| i<>j} , it can be either i>j or j>i , so it can not be DCFL . Am I correct ?

Same is the case with option D. Is this correct approach ?

+11

let i,j>=0
*L*2={0^{i}1^{j }∣ *i*=*j*}

S → 0S1 | ^
*L1*={0^{i}1^{j }∣ *i *≠ *j*} either 0's are more , 0^{+}0^{i}1^{j} or 1's are more 0^{i}1^{j}1^{+}

S→ AX|XB ,

X→0X1|^ ,

A→0A|0 ,

B→ 1B|1

*L*3={0^{i}1^{j }∣ *i*=2*j*+1}

0^{2j+1}1^{j }* that is *00^{2j}1^{j}

S→0X

X→00X1 | ^

*L*4={0^{i}1^{j }∣ *i*≠2*j *} either 0's are more 0^{+}0^{2j}1^{j }or 1's are more 0^{2j}1^{j}1^{+}

S →AX|XB

X→ 00X1|^

A→ 0A|0

B→ 1B|1

0

Hello, I have a doubt, as far I know, Complement of a CFL is not closed. If L = a^i b^j is $a^{i}b^{j}$ where i!=j , then its complement would be L (complement) a^{i}b^{j} where i == j. Hence the complement if not CFL.

Please correct me....

+2

For L3, pushing two 0's would have worked if j=2i+1, i.e if number of 1's were more than the number of 0's. But in this case number of 0's is more than the number of 1's.

e.g. 0000011 is a valid string for L3. How can this be processed by a PDA?

e.g. 0000011 is a valid string for L3. How can this be processed by a PDA?

+3

do nothing for first 0, then push one 0 one reading 2 0's ( one push ,one do thing) , then read one 1 pop one 0

+1

here there is a mistake in the solution , the logic of pushing two 0 for each 0 is wrong for l3 and l4

0

L3 = 1st "0" do nothing. then "**for every 2 0's push one 0 on stack" and for every "1" pop one "0"**

That's it, You'll reach end of string and stack has only stack alphabet, POP it and accept. {e,z0/e}

0

For L3, we can pop two 0s for one 1, and after all 1s are over, if the top has 0, pop it. If stack becomes empty, then accept, else reject.

0

@ARJUN sir, In the first case I think when they are saying i≠j, then there are two possibilities i<j or i>j but at a time only one will occur (because of OR), and we need only one stack to perform this action , when we come to make PDA then there will be 2 PDA's 1st be will i<j and second will be i>j. Thats why this is DCFL . if in a case i<j and i>j it will CSL because we need 2 stacks. Am I right sir?

- All categories
- General Aptitude 1.5k
- Engineering Mathematics 7.1k
- Digital Logic 2.7k
- Programming & DS 4.9k
- Algorithms 4.2k
- Theory of Computation 5.3k
- Compiler Design 2.1k
- Databases 4k
- CO & Architecture 3.5k
- Computer Networks 4k
- Non GATE 1.4k
- Others 1.5k
- Admissions 559
- Exam Queries 555
- Tier 1 Placement Questions 23
- Job Queries 69
- Projects 18

47,935 questions

52,336 answers

182,393 comments

67,819 users