Construindo todas as linguagens sem contexto a partir de um conjunto de linguagens de base e propriedades de fechamento?

10

Uma maneira de observar expressões regulares é como uma prova construtiva do seguinte fato: é possível construir os idiomas regulares iniciando com um pequeno conjunto de idiomas e combinando-os por meio de um pequeno conjunto fixo de propriedades de fechamento. Especificamente, se começarmos com o idioma vazio, o idioma que contém a cadeia vazia e os idiomas de todas as cadeias de caracteres únicos, podemos montar todos os idiomas regulares possíveis usando a união, concatenação e estrela Kleene.

Existe um conjunto de linguagens de base e propriedades de fechamento que podem ser usadas para gerar todas e apenas as linguagens sem contexto? (Para esclarecer: não estou perguntando se você pode escrever expressões regulares para todas as CFLs, o que eu sei que é impossível. Em vez disso, estou me perguntando se existe uma maneira de criar uma estrutura de expressão regular para CFLs com base no mesmos princípios básicos.)

templatetypedef
fonte
11
Por acaso, uma de nossas perguntas de referência pode conter o que você precisa.
Raphael

Respostas:

8

Isso é possível, mas talvez não exatamente da maneira que você pergunta. Como um começo tomar a linguagem Dyck de todas as cadeias de suportes correspondentes ao longo de dois pares de colchetes, dizem { [ , ] , ( , ) } , ou mais abstratamente a 1 , b 1 , a 2 , b 2 .D2{[,],(,)}uma1 1,b1 1,uma2,b2

Então, cada linguagem livre de contexto pode ser obtida a partir de usando homomorphisms, homomorphisms inversas e intersecção com linguagens regulares. As linguagens livres de contexto são chamadas "o cone principal gerado por D 2 ", em livros antigos denotados M ( D 2 ) . Veja uma pergunta relacionada: " Quais idiomas são reconhecidos por máquinas de balcão único? "D2D2M(D2)

De fato, precisamos apenas de uma de cada operação (bem escolhida). Cada CFL pode ser escrita , onde g , h são homomorfismos e R é uma linguagem comum. Intuitivamente, R é um programa de um PDA, g mapeia cada instrução para a letra lida, h para as operações push e pop da pilha. Finalmente D 2 códigos de comportamento pilha adequada.g(h-1 1(D2)R)ghRRghD2

Esse resultado está relacionado ao teorema de Chomsky – Schützenberger (ou como pode ser visto na wikipedia, um deles). A afirmação vinculada aqui na wikipedia (a) não precisa de um homomorfismo inverso, enquanto (b) não se restringe a dois pares de colchetes. Teoremas desse tipo são da área de "Famílias abstratas de autômatos", onde Ginsburg e Greibach são nomes importantes. Um resultado relacionado por Nivat afirma que operações na forma para g , h , R fixo são as transduções em estado finito.eug(h-1 1(eu)R)g,h,R

Hendrik Jan
fonte
Uau, isso é realmente interessante! Se você tem alguma referência sobre isso, eu adoraria dar uma olhada!
Templatetypedef
Fantástico. Isso responde perfeitamente à minha pergunta.
templatetypedef