BNF

Question 1

What is a context-free language?

Answer 1

A context-free language is a set of strings and symbols that follow the rules of a context-free grammar.

Question 2

What is a context-free grammar (CFG)?

Answer 2

A CFG describes which strings are possible or not possible in a language by defining a set of production rules.

Question 3

What is a production rule in a CFG? Give examples.

Answer 3

A production rule specifies how one symbol can be replaced by another. Examples:

a → ab (a is replaced by ab)

a → aa (a is replaced by aa)

b → a (b is replaced by a)

Question 4

What is Backus-Naur Form (BNF)?

Answer 4

BNF is a way of notating context-free languages using statements where the left-hand side is defined by the right-hand side.

Question 5

What are non-terminals in BNF?

Answer 5

Non-terminals are syntactic variables placed inside angle brackets (e.g. <expr>). They can be broken down further into terminals, other non-terminals, or both.</expr>

Question 6

What are terminals in BNF?

Answer 6

Terminals are literal symbols (without brackets) that cannot be broken down further and must be taken as written values.

Question 7

What does the pipe (|) symbol represent in BNF?

Answer 7

It represents the OR operator, allowing alternatives in production rules.

Question 8

How does recursion work in BNF?

Answer 8

A non-terminal can be defined in terms of itself, allowing recursive definitions. This enables BNF to represent some strings that regular expressions cannot, because regex does not support recursion.

Question 9

Why is recursion important in BNF?

Answer 9

It allows representation of nested or repeating structures (e.g. balanced parentheses, nested expressions) which cannot be represented by regular expressions.

Question 10

What is a syntax diagram?

Answer 10

A syntax diagram is a visual representation of a regular language.

Non-terminals are shown as rectangles.

Terminals are shown as ellipses.

Arrows connect shapes to show how strings can be formed.

Question 11

How is each non-terminal represented in a syntax diagram?

Answer 11

Each non-terminal has its own separate diagram that defines its production rules visually.