Grammaire hors contexte

Définition: Soit $G = (V, \Sigma, S, R)$ une grammaire. $G$ est hors contexte si les règles de réécriture respecte les restrictions suivantes:

• Les termes de gauche consistent en un seul symbole non terminal.

Langage hors contexte

Définition: Un langage est dit hors contexte (ou non contextuelle) s’il existe une grammaire hors contexte qui le génère.

Automate à pile

Définition: Un automate à pile consiste en un sixtuplet de la forme $(S, \Sigma, \Gamma, \delta, \iota, F)$ où

• $S$ est un ensemble fini d’états.
• $\Sigma$ est l’alphabet d’entrée (alphabet du ruban).
• $\Gamma$ est l’alphabet de la pile.
• $\delta : S \times \Sigma_\lambda \times \Gamma_\lambda \to \mathcal P(S \times \Gamma_\lambda)$ est la fonction de transition.
• $\iota \in S$ est l’état initial.
• $F \subseteq S$ est l’ensemble des états finaux (ou accepteurs ou acceptants).

Aujourd'hui

• Langage hors contexte
• Révision

Théorème

$L$ est un language hors context si et seulement si un automate à pile accepte $L$.

Exercice

Donnez un automate fini non déterminites ayant 3 états qui accepte $$L = \{ w \mid w \text{ termine avec } 00 \}.$$

Exercice

Donnez un automate fini non déterminites ayant 3 états qui accepte le language décrit par $0^*1^*0^*0.$

Exercice

On dit que $x$ est un préfixe du mot $y$ si il existe $z$ tel que $xz = y$ et que $x \ne y$.

Soit un langage $A$ sur $\Sigma$. Montrez que le language

$$L = \{ w \in A \mid \text{ aucun préfixe de } w \text{ n'est dans } A \}$$

est régulier si $A$ est régulier.

Exercice

Soit le langage $L = \{ w \mid w $ n'est pas un palindrome $\}$. $L$ satisfait les 3 conditions du lemme de pompage. Est-ce que cela implique que $L$ régulier?

Exercice

Montrez que les languages hors contexte sont fermés sur les opérations: union, concaténation et fermeture.

Exercice

Soit l'alphabet $\Sigma = \{0, 1\}$ et soit $L$ le langage des mots qui contiennent le même nombre de $0$ que de $1$.

1. Donnez une grammaire hors contexte qui génère $L$.
2. Donnez un automate à pile qui accepte $L$.

Exercice

Soit l'alphabet $\Sigma = \{0, 1\}$ et soit $L$ le langage des mots qui contiennent deux fois plus de $0$ que de $1$.

1. Donnez une grammaire hors contexte qui génère $L$.
2. Donnez un automate à pile qui accepte $L$.

Exercice

Soit l'alphabet $\Sigma = \{0, 1\}$ et soit $$L = \{ xy \mid x, y \in \Sigma^* \text{ et } \lvert x \rvert = \lvert y \rvert \text{ mais } x \ne y \}$$

1. Donnez une grammaire hors contexte qui génère $L$.
2. Donnez un automate à pile qui accepte $L$.

Exercice

Soit $M = (S, \Lambda, \Gamma, \delta, \iota, F)$ un automate à pile qui peut accepter des séquences sans vider sa pile. Montrez qu'il existe un automate à pile $M' = (S', \Lambda', \Gamma', \delta', \iota', F')$ qui vide toujours sa pile avant d’accepter et tel que $L(M) = L(M')$.