Chapter 7 - Context-Free Grammars

Question 1

What is a context-free grammar?

Answer 1

A language that is more general than a regular expression, and is made up of these features:
A finite set (N) of nonterminal symbols - nonterminals
A finite set (T) of terminal symbols - terminals
A finite set (P) of productions - production is a sequence of terminal and nonterminal symbols
The start symbol (S)

Question 2

What does left-recursive and right-recursive mean?

Answer 2

Left-recursive = A -> Ax
Right-recursive = A -> xA

Question 3

What is a production (in simple terms)?

Answer 3

Basically, a chain. You can go from one symbol, to another which it corresponds to. This eventually will generate a valid word that is part of the language

Question 4

What is a linear grammar?

Answer 4

Has at most only one nonterminal symbol in its right-hand side.
These linear grammars are always regular languages.

Question 5

What is a derivation tree?

Answer 5

A derivation tree is a graphical representation of the process you follow when using a procedure to generate a word.

Question 6

What does ambiguity mean when it comes to derivation trees?

Answer 6

Ambiguity means that there are multiple trees which can represent the same word.
It can also mean multiple leftmost or rightmost derivations, which also results in the same word being formed.