a) Defina uma gramática de tipo 1 .
b) Dê um exemplo de uma gramática que não seja uma gramática de tipo 1.
c) Defina uma gramática de tipo 2 .
d) Dê um exemplo de uma gramática que não seja uma gramática de tipo 2 , mas que seja uma gramática de tipo 1.
e) Defina uma gramática de tipo 3 .
f) Dê um exemplo de uma gramática que não seja uma gramática de tipo 3 , mas que seja uma gramática de tipo 2.

Passo 1

O enunciado pede definições e exemplos de gramáticas segundo a hierarquia de Chomsky: tipo 1 (sensível ao contexto), tipo 2 (livre de contexto) e tipo 3 (regular), além de mostrar exemplos que violem cada tipo.

Passo 2

Uma gramática de tipo 1 (sensível ao contexto) é uma quádrupla (V,\Sigma,P,S) cujas produções em P têm a forma
\alpha A \beta \;\to\; \alpha \gamma \beta
com A\in V, \alpha,\beta\in(V\cup\Sigma)^* e \gamma\in(V\cup\Sigma)^+. Em outras palavras, nenhuma produção pode diminuir o comprimento da cadeia (não contrai), exceto possivelmente S\to\varepsilon se S não aparece no lado direito de nenhuma produção.

Passo 3

Um exemplo de gramática que não é tipo 1 é
G = \bigl(\{S\},\{a,b\},\{\,S\to aSb,\;S\to \varepsilon\},S\bigr).
Aqui a produção S\to\varepsilon contrai a cadeia e S aparece em aSb, violando a condição de não contração.

Passo 4

Uma gramática de tipo 2 (livre de contexto) é uma quádrupla (V,\Sigma,P,S) em que todas as produções têm a forma
A \;\to\; \gamma
com A\in V e \gamma\in(V\cup\Sigma)^*. Não há contexto ao redor de A.

Passo 5

Um exemplo de gramática que não é tipo 2 mas é tipo 1 é uma gramática para a linguagem \{a^n b^n c^n\mid n\ge1\}:
\begin{aligned} S &\to aSBC \mid abc,\\\ CB&\to BC,\\\ bB&\to bb,\\\ cC&\to cc. \end{aligned}
Há produções como CB\to BC com dois não-terminais no lado esquerdo, logo não é livre de contexto, mas não contrai, sendo sensível ao contexto.

Passo 6

Uma gramática de tipo 3 (regular) é uma quádrupla (V,\Sigma,P,S) cujas produções são direita-lineares ou esquerda-lineares, por exemplo, no caso direita-linear:
A \;\to\; aB\quad|\quad a\quad|\quad \varepsilon
com A,B\in V e a\in\Sigma, podendo permitir S\to\varepsilon apenas se S não aparece em nenhum lado direito.

Passo 7

Um exemplo de gramática que não é tipo 3 mas é tipo 2 é
G = \bigl(\{S\},\{a,b\},\{\,S\to aSb,\;S\to ab\},S\bigr).
Ela gera \{a^n b^n\}, é livre de contexto (cada produção tem um não-terminal só à esquerda) mas não é regular.

Resposta

a) Gramática de tipo 1: produções \alpha A\beta\to\alpha\gamma\beta com \gamma\neq\varepsilon (não contrai).
b) Exemplo não tipo 1: S\to aSb,\;S\to\varepsilon com S em contexto e contração.
c) Gramática de tipo 2: produções A\to\gamma com A\in V, \gamma\in(V\cup\Sigma)^*.
d) Exemplo não tipo 2 mas tipo 1: \;S\to aSBC\mid abc,\;CB\to BC,\;bB\to bb,\;cC\to cc.
e) Gramática de tipo 3: produções A\to aB\mid a\mid\varepsilon (direita-linear ou esquerda-linear).
f) Exemplo não tipo 3 mas tipo 2: S\to aSb\mid ab.

Exercícios de Livros Relacionados