Context Free Grammar for $L = \{0^n w 1^n \mid n \ge 0, w \in \{0, 1\}^*\}$

462 Views Asked by At

Title says it all. I'm trying to make sure I have the correct CFG for $L$ before I start converting it to GNF. I don't want to post my idea yet, as I don't want it to influence any of the replies.

Again, I need a CFG for

$$L = \left\{0^n w 1^n \mid n \ge 0, w \in \{0, 1\}^*\right\}$$

Thank you for any help.

1

There are 1 best solutions below

4
On BEST ANSWER

What I suggested in comments on the basis of misreading the language can be easily modified to give a CFG that actually does generate $L$:

$$\begin{align*} &S\to 0S1\mid A\\ &A\to\epsilon\mid 0A\mid 1A \end{align*}$$

The first production generates the surrounding $0^n\dots1^n$, and the $A$ then generates an arbitrary word over $\{0,1\}$ in the middle.