1
$\begingroup$

Been having some trouble trying to come up with a CFG for this language: all binary strings that contain least 2 1's and at most 2 0's

So far, I've come up with this:

S --> T | 0T | T0 | T0T | 00TT | TT00 | 0T0T | T0T0 | 0TT0 | T00T

T--> 1T | V

V--> 11Z | 1Z1 | Z11

Z--> 1Z | epsilon

I realize this is mostly likely incorrect/redundant, so any feedback would be extremely helpful. Thank you!

$\endgroup$
  • 3
    $\begingroup$ Your language is regular, so you can come up with a regular expression or a DFA/NFA for it, and then convert it to a context-free grammar. $\endgroup$ – Yuval Filmus May 18 '17 at 4:23
  • $\begingroup$ Why does V have three productions? One is enough. And T isn't needed at all. V derives "at least two 1s, no zeroes". T derives "at least two ones, no zeroes". $\endgroup$ – gnasher729 Jul 18 '17 at 0:03
  • $\begingroup$ Your grammar doesn't derive anything with only one 1 in a row, like 010111111111 or 0111111101. Or two zeroes in the middle, like 10101. Start by writing down what you want to derive from each non-terminal. $\endgroup$ – gnasher729 Jul 18 '17 at 0:06
1
$\begingroup$

Hint

If $L_{i j}$ is the language with at least $i$ $1$s and at most $j$ $0$s

$$\begin{align} L_{2 2} &= 1 \, L_{1 2} \, | \,?\\ ... \\ L_{0 0} &= \,? \end{align}$$


Edited to answer the correct question.

$\endgroup$
0
$\begingroup$

Your language is regular, for example it is described by the regular expression $$ 111^* + 111^*01^* + 1^*011^* + 101 + \\ 111^*01^*01^* + 1^*0111^*01^* + 1^*01^*0111^* + 1010 + 1001 + 0101. $$ You can convert this regular expression, or (better) a finite state automaton (deterministic or non-deterministic) accepting the language, into a context-free grammar.

$\endgroup$
0
$\begingroup$

I'll write down some simple productions, and on the right hand side I note the conditions for each non-terminal symbol. For example "A = ≥ 2, ≤ 1" means "A must produce a sequence containing ≥ 2 ones, and ≤ 1 zeroes".

S -> 0A | 1B       A = ≥ 2, ≤ 1. B = ≥ 1, ≤ 2
A -> 0C | 1D       C = ≥ 2, 0. D = ≥ 1, ≤ 1
B -> 0D | 1E       E = ≥ 0, ≤ 2
C -> 1F            F = ≥ 1, 0
D -> 0F | 1G       G = ≥ 0, ≤ 1
E -> 0G | 1E
F -> 1H            H = ≥ 0, 0
G -> 0H | 1G
H -> 1H | eps

We can take some shortcuts for non-terminals that have only one production or are only used once:

S -> 0011H | 01D | 10D | 11E
D -> 01H | 1G
E -> 0G | 1E
G -> 0H | 1G
H -> 1H | eps

Another advantage is that both grammars are unambiguous. For parsing, the first version is in LL(1), which is about the easiest kind of grammar for parsing.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.