AQA A Level · Computer Science 7517

Context-free languages: Practice Questions

5 multiple-choice questions marked as you go, and 5 written questions with worked solutions. All on Context-free languages.

10 questions30 marksFree, no account

Question 1

1 mark

Which of the following is the most accurate reason why Backus-Naur Form (BNF) is used to represent context-free languages instead of regular expressions?

Question 2

1 mark

Consider the following BNF production rules:
\(\langle expr \rangle ::= \langle digit \rangle \ | \ \langle digit \rangle \langle expr \rangle\)
\(\langle digit \rangle ::= 0 \ | \ 1 \ | \ 2 \ | \ 3 \ | \ 4 \ | \ 5 \ | \ 6 \ | \ 7 \ | \ 8 \ | \ 9 \)
Which of the following strings is NOT valid according to these rules?

Question 3

1 mark

A language \(L\) is defined by the following BNF grammar:
\(\langle S \rangle ::= a \langle S \rangle b \ | \ ab \)
Which of the following sets represents the language \(L\)?

Question 4

1 mark

Which of the following statements regarding context-free languages and their representation is correct?

Question 5

1 mark

A context-free language is being defined using Backus-Naur Form (BNF). Consider the following rules:

\( \langle S \rangle ::= \langle A \rangle | \langle A \rangle \langle S \rangle \)
\( \langle A \rangle ::= "(" \langle S \rangle ")" | "()" \)

Which of the following describes the set of strings generated by this grammar?

Question 6

3 marks

Explain why Backus-Naur Form (BNF) is required to describe some languages that cannot be defined using regular expressions.

Write your answer out first, then check it against the worked solution.

Question 7

5 marks

A programmer is developing a compiler for a new programming language. Explain why Backus-Naur Form (BNF) must be used to define the syntax of the language instead of a regular expression if the language allows for nested parentheses to any depth.

Write your answer out first, then check it against the worked solution.

Question 8

5 marks

A student needs to define a syntax for nested mathematical expressions where brackets must always be balanced. Explain why a syntax diagram or BNF is a better choice for this than a regular expression.

Write your answer out first, then check it against the worked solution.

Question 9

5 marks

A language is described using Backus-Naur Form (BNF). Consider the following production rules for a simplified arithmetic expression:
<expression> ::= <term> | <term> "+" <expression>
<term> ::= <digit> | <digit> "*" <term>
<digit> ::= "2" | "3"

(a) Explain why this language is considered context-free rather than regular.
(b) Provide a derivation or draw a syntax diagram to show that the string "2*3+2" is valid according to these rules.

Write your answer out first, then check it against the worked solution.

Question 10

7 marks

Backus-Naur Form (BNF) is used to define the syntax of context-free languages.

(a) Explain why a regular expression cannot be used to define a language that requires matching balanced parentheses of any depth, while BNF can.

(b) Given the following BNF rules:
\( \langle expr \rangle ::= \langle term \rangle | \langle term \rangle "+" \langle expr \rangle \)
\( \langle term \rangle ::= "x" | "(" \langle expr \rangle ")" \)
Show the derivation for the string "x+(x)".

(c) Identify the recursive element in the rules above and explain its significance.

Write your answer out first, then check it against the worked solution.

* The content provided by thinka is generated by AI and may not always be accurate or up-to-date. Please use it as a supplementary resource and verify with official materials.

You've seen the model answer. Now get yours marked.

This page can show you how a good answer looks. It cannot tell you what your answer was missing. thinka marks your written work against the real mark scheme in about 15 seconds.

Get My Answers Marked Back to the notes

Want more questions like these? Get a fresh set on this topic, marked as you go.