# FLC - lesson 04
##### 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


### ambiguity

#### Syntax tree derivation