lesson_05.md 1.2 KB
FLC - lesson 05
Luca Oddone Breveglieri
15 october 2015
Grammars pt.II
In writing a grammar one needs to pay attention that every non-terminal is defined, and it is useful, to avoid useless rules
A grammar is in its reduced form if:
- Every non-terminal A is reachable from the axiom
- Every non-terminal A generates a non-empty set of strings.
Reduction of the grammar
There is an algorithm in two phases:
- Identifying the non-terminal symbols that are undefined
- Identifying the non-terminal symbold that are unreachable
The resulting grammar can be reduced but is not guaranteed to be minimal
Phase 1
Construct the complement set DEF and the defined non-term symbols $$DEF=V\setminus UNDEF$$
Phase 2
A third rule is required for a grammar to be in the reduced form,
The grammar G must not have circular derivations, which are inessential and lead to ambiguity
To obtain a non-circular grammar we have to:
- Remove the copy rules
- Remove the null rules
Recursion is also common in grammars,
It is a required and sufficient condition for a reduced grammar to generate infinite languages
$A\overset{n}{\Rightarrow} xAy\;\;n\ge 1$ is recursive