Linguagem sensível ao contexto

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

Na teoria de linguagens formais, uma linguagem sensível ao contexto é uma linguagem gerada por alguma gramática sensível ao contexto. O conjunto de todas as linguagens sensíveis ao contexto é idêntico ao conjunto de linguagens aceitas por um autômato linearmente limitado. De acordo com a Hierarquia de Chomsky, linguagens sensíveis ao contexto são Tipo-1.

Ícone de esboço Este artigo sobre Informática é um esboço. Você pode ajudar a Wikipédia expandindo-o.
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