grammatica acontestuale (CFG)

todo

• forma normale di Chomsky

Esercizi: formalizzare le descrizioni dei seguenti linguaggi in CFG

1. $L_1=\{w\in {\{0,1\}}^{\star }:{\#}_1(w)\ge 3\}$

$$\begin{gathered} S\to A1A1A1A \\ A\to 0A\mid 1A\mid \epsilon \end{gathered}$$

Stringhe binarie con almeno 3 uno

2. $L_2=\{w\in {\{0,1\}}^{\star }:w=w^R,|w|=2nn\in \mathbb{N}\}$

$w=w^R$ vuol dire palindroma.

$$\begin{gathered} S\to A \\ A\to 0A0\mid 1A1\mid 00\mid 11 \end{gathered}$$

3. $L_3=\{a^i{b}^i{c}^k:i+1=ki,k\ge 0\}$

$$\begin{gathered} S\to Xc \\ X\to YXc \\ Y\to aYb\mid \epsilon \end{gathered}$$

xc yxc aybyxcc aaybbyxcc → no ?