Exam-style question
Try this first
Explain why the language of balanced parentheses with arbitrary nesting can be described using BNF but cannot be represented using a regular expression. Include a suitable recursive production rule and explain its role.
Model answer
What a good answer should say
- A suitable rule is <S> ::= "(" <S> ")" <S> | empty.
- The rule can refer to <S> inside a pair of parentheses, so it can describe nesting such as "((()))".
- The final <S> allows another balanced section to follow, such as in "()()".
- The empty alternative provides a stopping case.
Explanation
Why this works
A strong answer identifies recursion as the important feature of BNF and connects it to unlimited nesting. It should also explain that the empty alternative terminates the recursive process and that regular expressions cannot represent this complete language.
Common mistake
No common mistake is linked to this question yet.