edited by
1,430 views
3 votes
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?

edited by

1 Answer

1 votes
1 votes

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

edited by

Related questions

1 votes
1 votes
1 answer
1
1 votes
1 votes
1 answer
3
aditi19 asked Mar 7, 2019
821 views
what is the CFG for the language L=w where number of a’s in w+number of b’s in w=number of c’s in whow to approach this?
0 votes
0 votes
1 answer
4
aditi19 asked Mar 2, 2019
778 views
S->A | BA→ εB->aBbB->bwhat is the complement of the language of this grammar?