1

Let $\Sigma = {0, 1}$. Write CFG that generates the following language {w | w contains at least two 1’s}

I'm not really sure how to write a CFG that generates a language, so this is my attempt...

S-> A1A1A

A->0A1|1A0|AA|$\epsilon$

I'm not sure about the start, maybe it should be

S->A1A

A->1A1|1A0|0A1|$\epsilon$

I really don't know what I'm doing, so any pointers for how I can solve this problem (and the next ones I need to solve) would be hugely helpful!

From what I can tell my answers make no sense since I don't really understand what I'm doing. Another example of what I have thought of as a possible solution is:

$S_0 \implies 0S_0 | 1S_1$

$S_1\implies0S_1|1S_2$

$S_2\implies0S_2|1S_2|\epsilon$

but I'm not sure if this works for more than two 1's or if it works at all for that matter.

Sarah
  • 263
  • First, please spell out the language you want the CFG to accept more clearly - what's the $w|w$ in the title supposed to mean? Also, please explain why you don't think your attempts work? How did you construct them in the first place? – fgp Mar 19 '14 at 00:35
  • 1
    Here is a hint: Given a word $w$, you are interested in whether it has zero, one, or more $1$'s. Also, if a word has more than one $1$, then we know that we need to accept it. So, we see that there are three important states that we need to keep track of... – tci Mar 19 '14 at 00:57
  • I think you are on the right track with the edit. Perhaps it would help to write down which are the start symbols, which are the start symbols etc there. – tci Mar 19 '14 at 01:00
  • I'm really sorry, and this probably makes me seem fairly dumb but I don't really understand any of the 3 possibly solutions I wrote. I know that I want to accept strings that have at least two 1's, so I need to use something like S->A1A1A (so there can be anything, a 1, anything another one and anything, where anything is null, 0 or 1, but beyond that I'm not sure how to write it, or what to do with that information – Sarah Mar 19 '14 at 01:06

2 Answers2

3

Hint:

  • The regular expression for this language is $(\Sigma^*1\Sigma^*1\Sigma^*)$.
  • The grammar for the full language is $F \to 0F \mid 1F \mid \ldots \mid \varepsilon$.
  • The context-free grammars can be sometimes unbelievably close to regular expressions...

I hope this helps $\ddot\smile$

dtldarek
  • 37,381
  • This is a huge help, I really don't understand anything in my notes and I can't find any clear guides as to how I should build my rules – Sarah Mar 19 '14 at 01:03
  • 1
    @Sarah Well, your first attempt was pretty close, it's not a coincidence that I written the regular expression explicitly and hinted to look for similarities. – dtldarek Mar 19 '14 at 01:08
2

Your start $A \to A1A1A$ looks good, in that it can only make strings having two 1's and also has room to put arbitrary strings of 0,1 (possibly empty strings) at the beginning, between the 1's, or after the two you have guaranteed. It would seem simpler here to add the rules $A \to 1A|0A|\epsilon$ which would allow the construction of the arbitrary strings at the beginning, between the initial 1's and at the end.

This method of course doesn't give unique derivations.

EDIT The above doesn't work, the A has to switch to B first. So $A\to B1B1B$ and then $B \to 0B|1B|\epsilon.$ The above way allows in other strings without the two guaranteed 1's.

coffeemath
  • 29,884
  • 2
  • 31
  • 52
  • what do you mean by unique derivations? – Sarah Mar 19 '14 at 01:02
  • 1
    Well suppose I wanted to make the word w: 010010101. I could start by letting the 1's of A1A1A be any of the three pairs of 1's in w, and then go on. This woud end up with different sequences of allowable moves each ending up with the same string w. [Note I don't think unique derivations are usually required in CFG's anyway.] – coffeemath Mar 19 '14 at 01:05
  • why does A have to switch to B? – Sarah Mar 19 '14 at 01:11
  • 1
    If A stayed A, then using the other rules $A \to 1A|0A|\epsilon$ would give the language of all strings, even those not containing two 1's. – coffeemath Mar 19 '14 at 01:13
  • so then a complete solution would be $A\implies1A|0A|\epsilon$, $A\implies B1B1B$, $B\implies B1B1B$ ? – Sarah Mar 19 '14 at 01:18
  • Sarah: If A is the start symbol, you need the first one to be $A \to B1B1B$ to get the thing going, and after that make it possible to put anything where the B's are located, hence the $B \to 0B|1B|\epsilon.$ The attempt in your comment would (if A is the start) accept the empty string, as you have the production $A \to \epsilon$ in the first set. – coffeemath Mar 19 '14 at 01:32
  • let us continue this discussion in chat – coffeemath Mar 19 '14 at 01:34