Gramática irrestrita
Em Teoria da computação, a Gramática irrestrita é 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.
Uma gramática irrestrita é uma gramática formal G = ( N , Σ , P , S ) {\displaystyle G=(N,\Sigma ,P,S)} , onde N {\displaystyle N} é um conjunto de símbolos não-terminais, Σ {\displaystyle \Sigma } é um conjunto de símbolos terminais, P {\displaystyle P} contém as produções da forma α → β {\displaystyle \alpha \to \beta } onde α {\displaystyle \alpha } e β {\displaystyle \beta } são cadeias de símbolos em N ∪ Σ {\displaystyle N\cup \Sigma } e α {\displaystyle \alpha } não é uma cadeia vazia. Além disso, S ∈ N {\displaystyle 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 {\displaystyle N} e Σ {\displaystyle \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.
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 {\displaystyle G} , existe alguma máquina de Turing capaz de reconhecer L ( G ) {\displaystyle 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 {\displaystyle 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 {\displaystyle G} . M {\displaystyle M} é como segue: É fácil perceber que esta máquina de Turing irá gerar todas (e apenas) as sentenças de G {\displaystyle G} na segunda fita depois que o último passo for executado um número arbitrário de vezes. Assim a linguagem L ( G ) {\displaystyle 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.
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).
