The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+3 votes

Let $L=\{w \mid w \in (0+1)^+  , N_0(w) \le N_1(w) \le 2N_0(w) \}$,where $N_i(w)$ represents number of $i's$ in string $w$.

a) Give a CFG for $L$

b) is Lc =  Σ*- L context - free?

c) Let $\frac{1}{2}$L = $\{x | ∃y ∈ L , |x| = |y| , x.y ∈ L \}$.is $\frac{1}{2}$L context-free?

asked in Theory of Computation by Active (4.2k points)
edited by | 209 views
No it will be context-free

L can be written as L= {w | w ∈ (0+1)+ , N1(w) =N0(w) } U {w | w ∈ (0+1)+ , N1(w) =N0(w)+1 } U {w | w ∈ (0+1)+ , N1(w) =N0(w)+2} U..........U {w | w ∈ (0+1)+ , N1(w) =2N0(w) } .Each of them individually itself context-free.So union is context-free.

Why can't we apply this union approach to $a^{n}b^{n}c^{n}$ to make it CFL?!

Akhilesh Singla  how would you do union for this language?

@Sambit I think you are taking union on infinitely many context free languages so the result may not be context free.

By the way can u please tell me the source of the problem.

1 Answer

+1 vote

a) $w$ will be CFL. Now how it will be CFL? Say grammar starts with 1.

So, first push 1,

Now, when 0 comes pop 1 with 0

if some extra 0 come push them in stack

then again when 1 comes pop 0 with 1

and like that we need to proceed, until it is empty stack.

[We can think grammar like this

$S\rightarrow 0S1|0S11|1S0|11S0|10S1|1S01|1|01|011|10|110|101$, but it is not a fully correct grammar]

It cannot be represented with a grammar

b)Complement of L will be $\left \{w|w\epsilon \left(0+1 \right ) ^{*}\right \}$ where $N_{0}\left ( w \right )>N_{1}\left ( w \right )$ or $N_{1}\left ( w \right )>2N_{0}\left ( w \right )$

c)yes it will be CFG.

Say grammar is $L=0^{n}1^{n}$

then $\frac{1}{2}L$ will be subset of $0^{n}1^{n}$. Now subset of CFG will be CFG or regular.

For example $L=0^{n}1^{n}$

and $1/2L=0^{n}$ which will be $0^{*}$ or $0^{*}1^{*}$

or it could be $0^{n/2}1^{n/2}$ , which is CFL

So, will be Regular or CFL

answered by Veteran (106k points)
edited by
Ankit can u please show that how ur grammar generates the string 01110. I tried it but cant find.

Thanks a lot for ur effort
@kushagra ,

S ---> 0A

      >  01B1B

       > 01(epsilon) 1 B

       > 0111B0

       > 0111(epsilon)0

       > 01110
Oh yes now I get it I think your grammar is correct

Thanks a lot.

cannot generate 011110
yes b) is NCFL


Can we generate grammar for $ww^{r}$?
S-> 1S1 | 0S0 | epsilon

grammar for ww^r
@srestha , 011110 is not in the, no. of zeros+1 != no. of ones
yes, I got a grammar

$A\rightarrow B|\epsilon$

$B\rightarrow 0A1|1A0|1B1|1C1|0A11|01A1|11A0|1A10|10A1|1A01|1B11|11B1|1D11|11D1|C$

$C\rightarrow 0C0|0B0$

$D\rightarrow 0D00|0B00|00D0|00B0$
I came upto this

Still some extra string coming


why 011110 not in language? It is in
@srestha , yes , some extra string like 11101 is still coming but nice effort :)...In above , I have not written grammar  for original question ,I have written grammar for language where  no. of zeros+1 = no. of ones in the strings...

Related questions

+1 vote
2 answers

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

46,734 questions
51,201 answers
66,556 users