Gramáticas sensíveis ao contexto
Origem: Wikipédia, a enciclopédia livre.
Em Teoria da computação as Gramáticas sensíveis ao contexto é também conhecida como Tipo 1 da Hierarquia de Chomsky, se as regras de substituição forem impostas à restrição de que nenhuma substituição possa reduzir o comprimento da forma sentencial à qual a substituição é aplicada, cria-se uma classe chamada sensíveis ao contexto.
Teoria de Autômatos: Linguagem formal e gramática formal | |||
---|---|---|---|
Hierarquia Chomsky |
Gramática | Linguagem | Reconhecedor |
Tipo-0 | Estrutura de frase | Recursivamente enumerável | Máquina de Turing |
-- | Estrutura de frase | Recursiva | Máquina de Turing |
Tipo-1 | Sensíveis ao contexto | Sensíveis ao contexto | Máquina de Turing com memória limitada |
Tipo-2 | Livre de contexto | Livre de contexto | Autômato com pilha |
Tipo-3 | Regular | Regular | Autômato finito |