0

I have first created the following CFG for the same number of 0's and 1's:

S → S0S1S | S1S0S | ε

To create more 0's than 1's, do I need to introduce a new variable such as the following?

S → SAS1S | S1SAS | 0A
A → 0A | 0

But it's not working!

afarin af
  • 1

1 Answers1

1

The problem with the rule $$S \to SAS1S \mid S1SAS \mid 0A,$$ is that, as soon as a $1$ is introduced, you are automatically spawning many more zeros all around the $1$. For example, you couldn't make the string $001$ with the given rules. Instead, consider creating the rule $S \to \varepsilon$ to allow each $S$ to be replaced with no $0$s (and no $1$s).

The above adjustment means that the string no longer satisfies $|w| \ge 2$, which we now need to address. What we'll need to do is replace $S$ with a new state, and have the starting state feed into it when we're comfortable that at least two symbols will be produced. Here's my suggestion:

\begin{align*} S &\to TAT1T \mid T1TAT \mid 0A \\ T &\to TAT1T \mid T1TAT \mid \varepsilon \\ A &\to 0A \mid 0. \end{align*}

user854214
  • 506
  • Thank you! I also came up with the following rule, where I am considering equal number of 0's and 1's or greater number of 0's than 1's: $\begin{align} S &\to T0S \mid T0T \mid 0T1TS \mid 1T0TS \mid 0T1T \mid 1T0T \mid 00\ T &\to 0T1T \mid 1T0T \mid 0 \\end{align} – afarin af Nov 30 '20 at 02:25