For a grammar in GNF, the RHS of every production has a single terminal
followed by a string of variables.
The procedure of getting a grammar in GNF is beyond the scope of this
book.
GLOSSARY
CFG: Context-Free Grammar.
Left-Linear Grammar: All productions are either of the form
V VT
→
*
or
V
T
→
*
Right-Linear Grammar: All productions are either of the form
V
T V
→
*
or
V
T
→
*
Parsing: Finding a derivation of the string.
Topdown Parsing: Sequence of rules applied in the leftmost derivation
Bottomup Parsing: Sequence of rules applied in a rightmost derivation.
Ambiguous Grammar: A CFG is said to be “ambiguous” if there exists at
least one string in the language of the CFG which is ambiguously
derivable. Otherwise it is unambiguous.
Useless Production: A production rule not affecting the language
Unit Production: Any production of a CFG of the form A B
→ where
A B V
, ∈ is called a Unit-Production.
Chomsky Normal Form: A CFG without any λ-productions is generated by
a grammar in which productions are of the form A BC
→
or A a
→ ,
where A, B ∈ V N and a V T
∈ .
REVIEW QUESTIONS
1. Define the term: Context-Free Grammar (CFG).
2. Give an example of a CFG.
3. What do you mean by a right linear grammar?
4. Show the relationship existing between right-linear grammars and
NFAs. Give an example.
5. What is a left-linear grammar?
6. Compare right-linear grammar with left-linear grammar.
7. Give some examples of Context-free languages.
8. What are derivation Trees?
Con text-free Grammars
149