Automatos

LINGUAGENS FORMAIS E AUTOMATOS

Nome: Yago Roberto Rodrigues da Silva RA:B0408D-9 Turma: CC6P14
1. Com seus conhecimentos, faça:
a) Uma descrição de cada um dos 4 níveis da Hierarquia de Chomsky;

Linguagens Enumeráveis Recursivamente:
Chamamos o tipo de gramática que definimos de tipo 0 ou recursivamente enumerável, estrutura de frase irrestritas. Não possui restrições nas regras de produção.

Linguagens Sensíveis ao Contexto: Se às regras de substituição for imposta a restrição de que nenhuma substituição possa reduzir o comprimento da forma sentencial à qual a substituição é aplicada, cria-se uma classe de gramáticas ditas sensíveis ao contexto. As gramáticas que obedecem a estas restrições pertencem, na hierarquia de Chomsky, ao conjunto das Gramáticas Sensíveis ao Contexto (GSC) ou do Tipo 1.

Linguagens Livres de Contexto: As Gramáticas Livres de Contexto (GLC) ou do Tipo 2 são aquelas cujas regras de produção são da forma:
A −> α onde A ∈ Vn, α ∈ V+
Ou seja, quando do lado esquerdo da regra há apenas um símbolo não-terminal (uma variável)

Linguagens Regulares: Aplicando-se mais uma restrição sobre a forma das produções, pode-se criar uma nova classe de gramáticas, as Gramáticas Regulares (GR), de grande importância no estudo dos compiladores por possuírem propriedades adequadas para a obtenção de reconhecedores simples, conhecido também como linguagem Tipo 3

b) Para cada nível dê exemplos práticos e explique os exemplos.

Linguagens Enumeraveis Recursivamente:
G= ( {S,A,B,C,D,E}, {a}, P,S )
P = { 1. S-> ACaB
2. Ca -> aaC
3. CB -> DB
4. CB -> E
5. aD -> Da 6. AD -> AC
7. aE -> Ea
8. AE -> k }
L(G) = {a2n | n é um inteiro positivo}

Linguagens Sensiveis ao Contexto:
G2 = ({S,C}, {a,b,c},P2,S)
P2 = { S -> abc ab -> aabbC
Cb -> bC
Cc -> cc }

Linguagens Livres de Contexto:
G = ({S,A,B}, {a,b}, P,S)
P = {S -> aB | bA
A -> a | aS | bAA
B -> b | bS | aBB }