Estou considerando o problema de reconhecer um idioma (acima do alfabeto 0-9 e espaço) contendo seqüências de caracteres como "1 2 3 4 5 6" e "14 15 16 17", mas não "1 3".
Isso surgiu durante o trabalho em uma tarefa de análise comum em que os elementos precisavam estar em uma lista ordenada. Percebi que, embora a análise do restante desse idioma fosse regular, essa parte era claramente irregular - ele pode reconhecer, por exemplo, o idioma A1A2 em que A é uma sequência arbitrária de 0 a 9. De fato, parece ser sensível ao conteúdo (e não isento de contexto pelo lema de bombeamento).
Minha primeira pergunta: existe uma classe (razoavelmente conhecida, ou seja, não definida apenas para esse problema) de linguagens entre sensíveis ao contexto e livres de contexto que descreva melhor seu poder expressivo? Eu li sobre as linguagens indexadas do Aho, mas não é óbvio (para mim!) Que estas são mesmo nessa classe, por mais poderosa que seja.
Minha segunda pergunta é informal. Parece que esse idioma é fácil de analisar e, no entanto, é muito alto na hierarquia. É comum encontrar exemplos semelhantes e existe uma maneira padrão de lidar com eles? Existe um agrupamento alternativo de classes de idiomas que é incompatível com a inclusão dos 'comuns'?
Minha razão para pensar isso é fácil: o idioma pode ser analisado deterministicamente, lendo até chegar ao final do primeiro número, verificando se o próximo número segue, e assim por diante. Em particular, ele pode ser analisado em O (n) tempo com O (n) espaço; o espaço pode ser reduzido para sem muitos problemas, eu acho. Mas já é difícil o suficiente para obter esse tipo de desempenho com linguagens regulares, sem falar no contexto.
fonte
Respostas:
Parece que o que você está procurando são autômatos de cabeças múltiplas (no seu caso, autômatos finitos determinísticos de 1 via e 2 cabeças devem ser suficientes). Não sou especialista nisso, mas o Google exibe algumas pesquisas interessantes sobre essa hierarquia de idiomas, como
Marek Chrobak: Hierarquias dos autômatos de várias cabeças de mão única, http://www.sciencedirect.com/science/article/pii/0304397586900939
Isso também dá uma resposta para sua segunda pergunta: A hierarquia dos autômatos n-head está "do outro lado" da hierarquia de Chomsky.
fonte