上下文無關語言：練習題

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?

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?

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\)?

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

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?

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

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.

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.

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.

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.