Exam-style question
Try this first
Write simple BNF production rules for a language containing one or more lowercase letters from the set {a, b, c}. Then use the rules to show how the string "cab" can be generated.
Model answer
What a good answer should say
- <letter> ::= "a" | "b" | "c" <word> ::= <letter> | <letter> <word> One derivation of "cab" is: <word> => <letter> <word> => "c" <word> => "c" <letter> <word> => "c" "a" <word> => "c" "a" <letter> => "c" "a" "b"
Explanation
Why this works
The <letter> rule restricts each character to a, b, or c. The recursive <word> rule allows another letter to be added, while the alternative containing only <letter> provides the stopping case.
The derivation shows that "cab" is generated.
Common mistake
No common mistake is linked to this question yet.