0

I've encountered this in a book: The language $ \{ a^n0b^n \mid n ≥ 1\} ∪ \{a^n1b^{2n} \mid n ≥ 1\}$has no predictive grammar.

(A predictable grammar is that in which no two rules of production for a same symbol have the same starting symbol)

I don't understand it. If I'm reading the definition of the language right a grammar for it could be just

start -> a 0term b | a 1term bb

0term -> a 0term b | 0

1term -> a 1term bb | 1

Which seems predictable to me.

carllacan
  • 391
  • 1
    Your grammar does not generate the language. Not that union $\cup$ does not mean concatenation. Words in the language are for example $aa0bb$ and $aa1bbbb$, and $aa1bb$ and $aa0b$ are not in the language, because the number of $b$'s is not good. – zarathustra Jun 05 '14 at 19:42
  • Oh, right, I got it really wrong. But then there is no context-free grammar for this language, is it? – carllacan Jun 05 '14 at 19:55
  • 1
    @carllacan, CFGs are closed under union. – Karolis Juodelė Jun 05 '14 at 20:06
  • Then how about this one? [I tried to write here my new try but the formatting got messed up. I'll edit the one on my question, if that's ok] Would it describe the language? And if it does isn't it a predictable grammar?

    Thanks.

     – carllacan Jun 05 '14 at 20:14

1 Answers1

1

Your new grammar indeed generates the given language. Not that it is not predictable, though, since the axiom symbol has two production rules, and these rules both start with the terminal 'a'.

To see how not "predictable" this grammar is, consider the following problem: given $w$ in the language, your goal is to find a derivation of $w$ with the grammar, but you only get to see the characters of $w$ in order, and you are not allowed to go backwards.

For example, consider the two words $aa0bb$ and $aa1bbbb$. The only letter you see for those two words is 'a', and you can't yet decide which production rule you have got to use to start the derivation (here, you'd have to see up until the third character to decide). That is why the grammar is not "predictable".

zarathustra
  • 4,891