Predictability of a grammar

71 Views Asked by At

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.

1

There are 1 best solutions below

0
On BEST ANSWER

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".