edited by
833 views

1 Answer

Best answer
15 votes
15 votes

$L=\{0^i1^j0^k\mid j=i+k,i,j,k\geq 0\} =\{\epsilon,0110,011100,001110,\ldots\}$

Now, $L=\{0^i1^{i+k}0^k\mid i,k\geq 0\}$

Here, CFG will be:

  • $S \rightarrow S_1S_2$
  • $S_1 \rightarrow 0S_11\mid\epsilon$
  • $S_2 \rightarrow 1S_20\mid\epsilon$
edited by

Related questions

12 votes
12 votes
3 answers
1
go_editor asked Jun 1, 2016
1,537 views
Write a regular expression for all strings of $0$’s and $1$’s in which the total number of $0$’s to the right of each $1$ is even. Justify your answer.
1 votes
1 votes
0 answers
2
go_editor asked Jun 1, 2016
513 views
A connected, simple, undirected planar graph $G(V, E)$ is given where $V$ denotes the set of vertices and E denotes the set of edges. In $V$, there is a designated source...
2 votes
2 votes
2 answers
4
go_editor asked Jun 1, 2016
1,050 views
A block of bits with $n$ rows and $m$ columns uses horizontal and vertical parity bits for error detection. If exactly 4 bits are in error during transmission, derive an ...