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.
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
cujas produções em
têm a forma
com
,
e
. Em outras palavras, nenhuma produção pode diminuir o comprimento da cadeia (não contrai), exceto possivelmente
se
não aparece no lado direito de nenhuma produção.
Passo 3
Um exemplo de gramática que não é tipo 1 é
Aqui a produção
contrai a cadeia e
aparece em
, violando a condição de não contração.
Passo 4
Uma gramática de tipo 2 (livre de contexto) é uma quádrupla
em que todas as produções têm a forma
com
e
. Não há contexto ao redor de
.
Passo 5
Um exemplo de gramática que não é tipo 2 mas é tipo 1 é uma gramática para a linguagem
:
Há produções como
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
cujas produções são direita-lineares ou esquerda-lineares, por exemplo, no caso direita-linear:
com
e
, podendo permitir
apenas se
não aparece em nenhum lado direito.
Passo 7
Um exemplo de gramática que não é tipo 3 mas é tipo 2 é
Ela gera
, é 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
com
(não contrai).
b) Exemplo não tipo 1: com
em contexto e contração.
c) Gramática de tipo 2: produções com
,
.
d) Exemplo não tipo 2 mas tipo 1:
e) Gramática de tipo 3: produções (direita-linear ou esquerda-linear).
f) Exemplo não tipo 3 mas tipo 2: .
b) Exemplo não tipo 1:
c) Gramática de tipo 2: produções
d) Exemplo não tipo 2 mas tipo 1:
e) Gramática de tipo 3: produções
f) Exemplo não tipo 3 mas tipo 2: