Gramática irrestrita

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Question book.svg
Esta página ou secção não cita fontes confiáveis e independentes, o que compromete sua credibilidade (desde março de 2014). Por favor, adicione referências e insira-as corretamente no texto ou no rodapé. Conteúdo sem fontes poderá ser removido.
Encontre fontes: Google (notícias, livros e acadêmico)

Em Teoria da computação, a Gramática irrestrita (conhecida também como Gramática com estrutura de frase) é também conhecida como Tipo 0 da Hierarquia de Chomsky, que são aquelas às quais nenhuma limitação é imposta. São capazes de gerar linguagens recursivamente enumeráveis. O universo das linguagens que se podem definir através dos mecanismos gerativos definidos pela gramática corresponde exatamente ao conjunto das linguagens que esta classe de gramática é capaz de gerar.

Definição formal[editar | editar código-fonte]

Uma gramática irrestrita é uma gramática formal , onde é um conjunto de símbolos não-terminais, é um conjunto de símbolos terminais, contem as produções da forma onde e são cadeias de símbolos em e não é uma cadeia vazia. Além disso, é o símbolo inicial. Como o nome implica, não há restrições nos tipos de produções que gramáticas irrestritas podem ter.

Vale notar que e não são necessariamente disjuntos, uma vez que gramáticas irrestritas não fazem distinção entre símbolos terminais e não-terminais. Tal distinção existe apenas para indicar quando parar ao gerar sentenças da gramática.

Gramáticas irrestritas e máquinas de Turing[editar | editar código-fonte]

Pode ser mostrado que gramáticas irrestritas caracterizam as linguagens recursivamente enumeráveis. Isto é o mesmo que dizer que para toda gramática irrestrita , existe alguma máquina de Turing capaz de reconhecer e vice-versa. Dada uma gramática irrestrita, tal máquina de Turing é simples de construir como uma máquina de Turing não-determinística , de duas fitas. A primeira fita contém a entrada w a ser testada e a segunda fita é usada pela máquina para gerar sentenças de . é como segue:

  1. Comece na esquerda da segunda fita e repetidamente escolha entre mover para a direita ou selecionar a posição atual da fita.
  2. De modo não-determinístico, escolha uma produção das produções em .
  3. Se aparecer em alguma posição na segunda fita, substitua por neste ponto, possivelmente deslocando os símbolos da fita para a esquerda ou direita dependendo dos tamanhos relativos entre e , i.e., se for maior que , desloca os símbolos da fita para a esquerda.
  4. Compare a sentença resultante na fita 2 com a palavra da fita 1. Se forem iguais, aceite. Caso contrário, volte para o passo 1.

É fácil perceber que esta máquina de Turing irá gerar todas (e apenas) as sentenças de na segunda fita depois que o último passo for executado um número arbitrário de vezes. Assim a linguagem é recursivamente enumerável. A construção reversa também é possível. Dada uma máquina de Turing, é possível criar uma gramática irrestrita.

Propriedades computacionais[editar | editar código-fonte]

Como pode ser esperado da equivalência entre gramáticas irrestritas e máquinas de Turing, o problema uma cadeia w pertencer ou não à linguagem de uma gramática irrestrita é indecidível. É perfeitamente possível criar uma gramática irrestrita universal, capaz de aceitar qualquer linguagem de outra gramática irrestrita, dada a descrição da linguagem, assim como é possível criar uma máquina de Turing universal. Assim, seria teoricamente possível construir uma linguagem de programação baseada em gramáticas irrestritas (e.g. Thue).

Ver também[editar | editar código-fonte]


Teoria de autômatos: linguagem formal e gramática formal
Hierarquia
Chomsky
Gramática Linguagem Reconhecedor
Tipo-0 Irrestrita Recursivamente enumerável Máquina de Turing
-- -- Recursiva Máquina de Turing que sempre para
Tipo-1 Sensível ao contexto Sensível ao contexto Autômato linearmente limitado
Tipo-2 Livre de contexto Livre de contexto Autômato com pilha
Tipo-3 Regular Regular Autômato finito