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 T
fl.formal-languages
context-free-languages
Alexander Rubtsov
fonte
fonte
Respostas:
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)
fonte