# FLC - lesson 04
##### Luca Oddone Breveglieri
###### 12 october 2015
## Free Grammars pt.I

### Grammars
Are meant to overcome the limits of regexp  
Are composed by:
- A __starting language__
- A __set of rules__ which can be applied a finite number of times

A language can be defined by rules that after multiple applications allow to generates all and only the phrases in the language  
### Context-free grammars

##### example 1:
__Language__
$$L=\{uu^R|u\in \{a,b\}^*\}=\{\varepsilon,aa,bb,abba,baab,...,abbbba,...\}$$
__Grammar rules__
$\text{frase}\rightarrow \varepsilon$  - The empty string is a valid phrase
$\text{frase}\rightarrow a\;\text{frase}\;a$ - A phrase encloses in a, a it's a phrase
$\text{frase}\rightarrow b\;\text{frase}\;b$ - A phrase encloses in b, b it's a phrase
<!--*-->
__Derivation chain__
$$\text{frase}\Rightarrow a\;\text{frase}\;a$$
Lista, frase are __non-terminal__ symbols
##### example 2:
__The metalanguage of regular expressions__

__alphabet__ $\Sigma_{r.e.}=\{a,b,\cup,*,\emptyset,(,)\}$ <!--*-->
__syntax__
$1.\;espr \rightarrow\emptyset$
$2.\;espr \rightarrow a$
$3.\;espr \rightarrow b$
$4.\;espr \rightarrow (espr\cup espr)$
$5.\;espr \rightarrow (espr\;espr)$
$6.\;espr \rightarrow (espr)^*$
<!--*-->
### Backus Normal Form - BNF

Is defined using four entities
- $V$ non-terminal alphabet
- $\Sigma$ terminal alphabet
- $P$ syntactic rules
- $S\in V$ is a particular non-terminal called *axiom*

Each rule $P$ is a pair $(X,\alpha)$ of:
- $X\in V$ element of the non-terminal alphabet
- $\alpha\in(V\cup \Sigma)^*$ element of terminal or non-terminal alphabet

Some examples are:
- $X\rightarrow\alpha$
- $X\rightarrow\alpha_1|\alpha_2|...|\alpha_n$
- $X\rightarrow\alpha_1\cup\alpha_2\cup...\cup\alpha_n$
<!--*-->

### Reduction of the grammars
A grammar is in __reduced form__ or simply __reduced__ if both the following conditions hold:
- Every non-terminal A is reachable from the axiom $S\overset{*}{\Rightarrow}\alpha A\beta$
- Every non-terminal A generates a non-empty set of strings $L_A(G)\neq\emptyset$
<!--*-->
There exists an algorithm in two phases:
- The first phase identifies the non-terminal symbols that are undefined
- The second phase identifies those that ar unreachable

__Phase 1__  

- Construct the complement set $DEF$ of the defined non-term symbols.
$$DEF = V\setminus UNDEF$$
- Initially $DEF$ is set to contain the non-terminal symbols that are expanded by terminal rules
$$DEF:=\{A|(A\rightarrow u)\in P, \text{with}\;u\in\Sigma^*\}$$ <!--*-->
- Then the following transformation is applied repeatedly, until it converges
$$DEF:=DEF\cup\{B|(B\rightarrow D_1D_2...D_n)\in P\}$$
Each symbol $D_i$ is either a terminal or belongs to $DEF$

In every iteration of the first phase, two events are possible:
- New non-terminal symbols are identified and added to the set $DEF$
- the $DEF$ set does not change, which means that convergence has been reached, therefore the algorithm terminates.  

The non-terminal symbols that belong to the $UNDEF$ set can be eliminated along with the rules where they appear.

__Phase 2__

The identification of the non-terminal symbols that are reachable starting from the axiom $S$ can be reduced to the problem of the existence of a path in the graph associated with the following binary relation produce

$A\overset{produce}{\rightarrow}B \;\;\text{if and only if} \;\;A\rightarrow\alpha B\beta \;\;\text{with}\;\;A\neq B\;\;\;\alpha,\beta\;\text{are any strings}$

The non-terminal $C$ is reachable from the axiom $S$ if and only if
the graph of the binary relation *produce* contains a path from $S$ to $C$

A __third property__ is often required for a grammar to be in the reduced form:

The grammar G may not have __circular derivations__, which are inessential and moreover give raise to ambiguity

#### example

$$\{S\rightarrow a,\;A\rightarrow b\}\;\text{reduced to}\;\{S\rightarrow a\}$$

### Recursive grammars

To generate an __infinite language__, composed of an infinite number of strings,
it is necessary to allow derivations of *unbounded length*, this is called __recursive grammar__

$$A\overset{n}{\Rightarrow}xAy\;\;n\ge 1\;\;\text{is recursive}$$

__Necessary and sufficient__ condition for a language $L(G)$ to be __infinite__:
>where $G$ is a grammar in the reduced form and does not have any circular derivations,
is that $G$ admits recursive derivations

A grammar __does not contain__ recursion (or is recursion-free) if and only if
the __graph__ of the binary relation *produce* is __acyclic__