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 nenhuma fonte ou referência, o que compromete sua credibilidade (desde março de 2014).
Por favor, melhore este artigo providenciando fontes fiáveis e independentes, inserindo-as no corpo do texto por meio de notas de rodapé. Encontre fontes: Googlenotícias, livros, acadêmicoYahoo!Bing. Veja como referenciar e citar as fontes.

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 reconhecer 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 G = (N, \Sigma, P, S), onde N é um conjunto de símbolos não-terminais, \Sigma é um conjunto de símbolos terminais, P contem as produções da forma \alpha \to \beta onde \alpha e \beta são cadeias de símbolos em N \cup \Sigma e \alpha não é uma cadeia vazia. Além disso, S \in N é 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 N e \Sigma 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 G, existe alguma máquina de Turing capaz de reconhecer L(G) 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 M, 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 G. M é 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 \beta \to \gamma das produções em G.
  3. Se \beta aparecer em alguma posição na segunda fita, substitua \beta por \gamma neste ponto, possivelmente deslocando os símbolos da fita para a esquerda ou direita dependendo dos tamanhos relativos entre \beta e \gamma, i.e., se \beta for maior que \gamma, 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 G na segunda fita depois que o último passo for executado um número arbitrário de vezes. Assim a linguagem L(G) é 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