Qual é o significado das linguagens sensíveis ao contexto (Tipo 1)?

Como as linguagens do Tipo 3 da Hierarquia Chomsky podem ser reconhecidas por uma máquina de estado sem memória externa (por exemplo, um autômato finito), o Tipo 2 por uma máquina de estado com uma única pilha (por exemplo, um autômato push-down) e o Tipo 0 por uma máquina de estado com duas pilhas (ou, equivalente, uma fita, como é o caso das máquinas de Turing), como os idiomas do tipo 1 se encaixam nessa imagem? E que vantagens traz para determinar que um idioma não é apenas o Tipo 0, mas o Tipo 1?

As linguagens sensíveis ao contexto são exatamente as linguagens que podem ser reconhecidas por uma máquina de Turing usando espaço linear e não determinismo. Você pode simular uma máquina de Turing usando tempo exponencial, para poder reconhecer qualquer idioma em tempo exponencial. Observe que o problema de reconhecer algumas linguagens sensíveis ao contexto é , o que significa que temos certeza de que você não pode fazer melhor que o tempo exponencial.$PSPACE$

Comparando isso com os idiomas do tipo 0, isso significa que você pode pelo menos dizer algo sobre quanto tempo leva para reconhecer o idioma. Um idioma do tipo 0 pode até não ser decidível: o idioma de todas as máquinas de Turing que são interrompidas é uma linguagem do tipo 0, mas como reconhecer essa linguagem é exatamente o problema da interrupção, não é decidível.

Gramáticas sensíveis ao contexto não são muito úteis na prática. Ao contexto gratuitos gramáticas são intuitivos para trabalhar, mas como os exemplos na Wikipedia mostram , ao contexto sensíveis gramáticas muito rapidamente tornar-se um pouco confuso. Programas que usam espaço polinomial são muito mais fáceis de projetar (e a garante a existência de algum CSG equivalente que é polinomialmente maior que o uso de espaço do seu algoritmo).$PSPACE$

A razão de sua existência é que elas formam uma extensão muito natural de gramáticas sem contexto (você permite que o contexto determine quais produções são válidas). Provavelmente, isso inspirou Chomsky a defini-los e nomeá-los como idiomas do tipo 1. Lembre-se de que essa definição foi feita antes dos computadores se tornarem tão rápidos quanto hoje: é mais interessante para os teóricos da linguagem formal do que para os programadores.

Gramáticas irrestritas ficam ainda mais estranhas: não há mais a noção de 'expandir' um termo-terminal e substituí-lo por uma produção, possivelmente dependendo do contexto. Você também pode modificar livremente o contexto. Isso torna as gramáticas irrestritas ainda menos intuitivas para trabalhar: os programas são equivalentes e muito mais intuitivos.

$L$

$\mathcal{A}$$L(\mathcal{A})$

Em resumo, para classes menores, você precisa de menos poder computacional para resolver o problema de decidir se uma palavra pertence ao idioma.

Segundo a Wikipedia , Chomsky definiu gramáticas sensíveis ao contexto (isto é, tipo 1) para descrever a sintaxe das línguas naturais. Isso é um pouco diferente do que ocorre com outras classes de idiomas, que foram introduzidas para descrever famílias de strings usadas em matemática (por exemplo, a sintaxe de fórmulas aritméticas) em vez de idiomas naturais (por exemplo, a sintaxe de uma sentença gramaticalmente correta em inglês) .

Em idiomas sem contexto, em qualquer ponto da análise de entrada, o autômato está em um estado definido por sua pilha. Cada produção tem o mesmo comportamento ao consumir a entrada, independentemente de onde é usada.

Isso leva à propriedade interessante de que cada produção gera uma sublíngua da gerada pelas que estão mais profundas na pilha e, portanto, para cada par A e B de produções geradas e consumidas em qualquer entrada específica, temos três casos possíveis:

• a: A entrada consumida por A está completamente contida na entrada consumida por B; ou
• b: A entrada consumida por A contém completamente a entrada consumida por B; ou
• c: A entrada consumida por A é completamente separada da entrada consumida por B.

Isso implica que o seguinte nunca acontece:

• d: A entrada consumida por A se sobrepõe parcialmente à entrada consumida por B.

Em contraste com isso, em linguagens sensíveis ao contexto, o comportamento de cada produção depende de onde é usado; portanto, a entrada consumida em uma produção não é uma sub-linguagem das que estão mais profundas na pilha (na verdade, processando-a com um pilha não funcionaria). E nós temos essa possibilidade d pode acontecer.

No mundo real, um caso em que uma linguagem sensível ao contexto faria sentido é algo como denotar <b> texto em negrito </b>, <i> texto em itálico </i> e <u> texto sublinhado </u> essas tags html e deixe que elas se sobreponham, como "Este é um <u> texto com <i> tags </i> misturadas </u> sobrepostas </i>." Observe isso para analisar isso e descobrir se todas as tags iniciais correspondem às tags finais, um PDA não funciona porque não é livre de contexto, mas um LBA o fará facilmente.

Propriedades de fechamento

De todas as classes de idioma da hierarquia de Chomsky, apenas idiomas regulares e sensíveis ao contexto são fechados sob complementação . Portanto, esse é um tipo de recurso exclusivo de linguagens sensíveis ao contexto.

Ao contrário das linguagens sem contexto, o CS também é fechado sob produtos de interseção e reprodução aleatória .

Qualquer linguagem do tipo 1 pode ser reconhecida por uma máquina de Turing que usa apenas espaço linear (os chamados autômatos limitados lineares).

Os idiomas do tipo 1 podem ser decididos por autômatos delimitados lineares , que são máquinas de Turing não determinísticas que podem usar apenas uma parte da fita cujo tamanho é linear ao tamanho da entrada.

A hierarquia de Chomsky classifica gramáticas mais que idiomas. No entanto, ele não foi projetado para ter algo a ver com o número de fitas que um autômato deve reconhecê-lo, como você sugeriu para os Tipos 2 e 3, mesmo se houver um tipo de máquina de Turing que faça isso para as gramáticas do Tipo 1.

Você também deve observar que os idiomas das gramáticas do Tipo 0 não são todos reconhecidos por uma máquina de Turing, mas só podem ser enumerados por essa máquina: Tipo 0 significa recursivamente enumerável, e as máquinas de Turing reconhecem apenas idiomas recursivos.

A linguagem de programação moderna usa recursos sensíveis ao contexto o tempo todo; eles se enquadram em um subconjunto que pode ser decidido com eficiência.

Exemplos são análise de nome e tipo e inferência de tipo.

Muitos outros mencionaram que as línguas do Tipo 1 são aquelas que podem ser reconhecidas por autômatos delimitados lineares. O problema da parada é decidível para autômatos delimitados lineares, o que, por sua vez, significa que muitas outras propriedades que são computacionalmente indecidíveis para idiomas reconhecidos pelo Turning Machines são decidíveis para idiomas do Tipo 1.

É certo que a prova de que o problema da parada é decidível para autômatos limitados lineares baseia-se no fato de que, com uma quantidade finita de fita, eles só podem inserir um número finito de estados; loop e nunca vai parar. Essa prova aplica-se tecnicamente a todos os computadores reais (que também possuem memória finita), mas isso não traz nenhum benefício prático na solução do problema de interrupção dos programas executados neles.