The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+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 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?

+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

0

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

Thanks a lot for ur effort

- All categories
- General Aptitude 1.3k
- Engineering Mathematics 5.4k
- Digital Logic 2.1k
- Programming & DS 3.9k
- Algorithms 3.4k
- Theory of Computation 4.2k
- Compiler Design 1.6k
- Databases 3.1k
- CO & Architecture 2.7k
- Computer Networks 3.1k
- Non GATE 1.1k
- Others 1.4k
- Admissions 501
- Exam Queries 448
- Tier 1 Placement Questions 19
- Job Queries 62
- Projects 12

37,963 questions

45,465 answers

131,322 comments

48,377 users