0

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.

Brian M. Scott
  • 616,228
The Rationalist
  • 115
  • 4
  • I don’t think that you need to worry about influencing the answers; a great many folks here would rather see that you’ve got somewhere with it yourself. This one’s easy enough that I’d normally just give a hint anyway, but I’ll say that you can do it with a grammar that has just the initial non-terminal and three productions, two of them terminal. – Brian M. Scott Apr 11 '13 at 04:43
  • Would it simply be S -> 0S1 | 0 | 1 ? That was one of my first ideas, but it didn't seem to quite fulfill the 0,1 esterate properly. I mean, 0110101001101 wouldn't work in that CFG, even though it should. Thanks for the advice. – The Rationalist Apr 11 '13 at 05:00
  • My other idea was S -> 0W1 / W -> 0W | 1W | S That one seems to work so far, but I wanted to be sure before I started the long conversion process. – The Rationalist Apr 11 '13 at 05:02
  • It is indeed just $S\to 0S1\mid 0\mid 1$. $0110101001101$ isn’t in $L$, so you don’t want to generate it! – Brian M. Scott Apr 11 '13 at 05:02
  • I think that you’ve misunderstood what language $L$ is. The members of $L$ are the words of the form $$\underbrace{00\dots00}_nb\underbrace{11\dots11}_n$$ such that $n\ge 0$ and $b$ is either $0$ or $1$. It does not include, for instance, $01011$. – Brian M. Scott Apr 11 '13 at 05:04
  • But it says that w is an element of 0,1 esterate, which means w could be any combination of 0s and 1s, isn't that right? So, w could be an infinite amount of possible combinations of 0s and 1s. This is what I learned the asterisk to mean when given an alphabet. If it were just {0,1}, with no asterisk, then it would just be either 0 OR 1. – The Rationalist Apr 11 '13 at 05:07
  • Sorry, you’re right: I missed the star. My apologies. At this point I might as well write up a quick answer. – Brian M. Scott Apr 11 '13 at 05:10
  • Why is $L\ne{0,1}^*$? – Did Apr 11 '13 at 07:29

2 Answers2

1

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.

Brian M. Scott
  • 616,228
1

That language is regular, it is in fact $\{0, 1\}^*$: you can always take $n = 0$ (no 0 at the beginning, no 1 at the end, anything whatsoever in between). So a grammar would be:

$\begin{equation*} S \to 0 S \mid 1 S \mid \varepsilon \end{equation*}$

vonbrand
  • 27,812