Funções Racionais e CFL

8

No meu trabalho surgiu o problema da classificação CFL em imagens de funções racionais. Em outros termos, o que classe de linguagens formar línguas , para contexto fixo linguagem livre e transdutor de estados finitos determinística . Obtive alguns resultados fáceis, como a linguagem Dyck com duas chaves corresponde à CFL e a linguagem Dyck com uma chave é um subconjunto estrito da CFL, agora existem alguns problemas que ainda me interessam, mas não acredito que ninguém já o descobriram. Existem documentos sobre esse assunto? A classificação no Google de CFL ou Rational Functions (FST determinístico) + CFL fornece resultados ruins.L TT(L)LT

Alexander Rubtsov
fonte
2
O Teorema de Chomsky-Schützenberger cairia nessa família de resultados. Pessoas (ie Ginsburg e outros) se mudaram de lá para a noção de Famílias Abstratas de Idiomas (AFL).
Sylvain

Respostas:

3

Em geral, o determinismo do transdutor parece não haver uma reestruturação real. As escolhas que podem ser feitas por um transdutor podem ser movidas para o idioma de entrada. Se isso for bom para você, os objetos às vezes denotados são chamados de trio principal . Os exemplos incluem famílias de idiomas lineares , contador cego e contador de um turno (número fixo de contadores). A tese de Habilitação de Kluas Reinhardt (Contagem como método, modelo e tarefa em ciência da computação teórica, disponível on-line) contém um belo diagrama de inclusão de várias famílias (página 64).M(L)

Hendrik Jan
fonte