give cfg for the language

Question

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 L^c =  Σ*- L context - free?

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

Comments

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.

Answer 1

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

https://gateoverflow.in/93981/half-l

Comments

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

@ankit

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...