A hierarquia de Chomsky está desatualizada?

45

A hierarquia de Chomsky (–Schützenberger) é usada em livros didáticos de ciência da computação, mas obviamente cobre apenas uma fração muito pequena de linguagens formais (REG, CFL, CSL, RE) em comparação com o Diagrama de Zoológico de Complexidade completo . A hierarquia tem mais algum papel na pesquisa atual? Encontrei poucas referências a Chomsky aqui em cstheory.stackexchange, e no Complexity Zoo os nomes Chomsky e Schützenberger não são mencionados.

A pesquisa atual está mais focada em outros meios de descrição, exceto gramáticas formais? Eu estava procurando por métodos práticos para descrever linguagens formais com expressividade diferente, e me deparei com a crescente linguagem sensível ao contexto (GCSL) e linguagens visivelmente pushdown (VPL), que estão entre as linguagens clássicas de Chomsky. A hierarquia de Chomsky não deve ser atualizada para incluí-los? Ou não adianta selecionar uma hierarquia específica do conjunto completo de classes de complexidade? Tentei selecionar apenas os idiomas que podem caber nas lacunas da hierarquia de Chomsky, tanto quanto eu entendo:

REG (= Chomsky 3) ⊊ VPL ⊊ DCFL ⊊ CFL (= Chomsky 2) ⊊ GCSL ⊊ CSL (= Chomsky 1) ⊊ R ⊊ RE

Ainda não entendo onde "linguagens levemente sensíveis ao contexto" e "linguagens indexadas" se encaixam (em algum lugar entre CFL e CSL), embora pareça haver relevância prática para o processamento de linguagem natural (mas talvez algo de relevância prática seja menos interessante em pesquisa teórica ;-). Além disso, você pode mencionar GCSL ⊊ P ⊂ NP ⊂ PSPACE e CSL ⊊ PSPACE ⊊ R para mostrar a relação com as famosas classes P e NP.

Encontrei no GCSL e no VPL:

Eu também ficaria feliz se você souber de algum livro mais recente sobre gramáticas formais que também lide com VPL, DCLF, GCSL e gramáticas indexadas, preferível com ponteiros para aplicações práticas.

cc.complexity-theory automata-theory fl.formal-languages big-picture teaching Jakob
fonte
7
Um ponto secundário: não vejo a ausência dos nomes Chomsky e Schützenberger no zoológico da complexidade como uma evidência de que "a hierarquia de Chomsky está desatualizada". A hierarquia de Chomsky é uma noção na teoria formal da linguagem. O Zoológico da Complexidade é um site principalmente sobre a teoria da complexidade, embora contenha algumas noções na teoria formal da linguagem, como linguagens sem contexto. São campos relacionados, mas distintos. Seria desatualizado se não fosse mencionado em um livro na teoria formal da linguagem, mas não sei se é esse o caso.
Tsuyoshi Ito
7
Bom ponto, Tsuyoshi. Francamente, eu gostaria de ver um "Zoológico de Línguas Formais" com boa fundamentação teórica (referências a trabalhos de pesquisa!), Mas também recursos práticos. Por exemplo, existem dezenas de variantes de sintaxe da Backus-Naur-Form e variantes de expressões regulares (algumas delas nem sempre regulares). Ao lado da simples hierarquia de Chomsky, achei difícil obter uma imagem clara do estado atual da pesquisa em linguagens formais.
Jakob
Você também pode adicionar idiomas sem estrelas estritamente abaixo dos idiomas regulares. Eles são como regulares, mas sem a estrela Kleene. Bem conhecido. Bem comportado.
Wren romano
Como várias respostas me mostraram, as gramáticas formais à la Chomsky são um método histórico para descrever linguagens formais, que atingiu seus limites. Ainda estou procurando uma boa visão geral das gramáticas formais, que não estão focadas na teoria da complexidade, mas obrigado por todas as referências adicionais! Aceito a resposta de mgalle porque ele tem menos reputação até agora.
Jakob
2
Em ciência da computação, design de linguagem de computador, design e programação de software, gramáticas e linguagens livres de contexto e expressões regulares e linguagens são equipamentos básicos de trabalho e tão importantes quanto sempre. Mas, para gramáticas arbitrárias, LBAs e linguagens sensíveis ao contexto, por outro lado, tenho visto poucas aplicações ou nenhuma.
Reinierpost

Respostas:

20

Pelo que vi na comunidade de Processamento de linguagem natural, as gramáticas formais à la Chomsky não são mais usadas. Eles (também) pensam que a Hierarquia de Chomsky está desatualizada para modelar a linguagem.

O que aconteceu foi o de reescrever a regra (o algoritmo de Lars), modelos de dependência (Dan Klein), gramática de substituição de árvores (o modelo DOP), gramáticas de recursos binários (Alex Clark).

mgalle
fonte
Relendo minha resposta, parece mais negativo do que eu queria que fosse. RL e CFL nunca deveriam ser modelos realísticos de linguagem natural, e a maioria dos "novos" modelos é realmente inspirada neles.
mgalle
Eu pensei que o RL nem sequer era projetado como um modelo de linguagens naturais, mas como um modelo de algum comportamento do sistema. [O texto original de Kleene também não usa a terminologia da linguagem formal.]
DG_
26

Em resumo: sim.

Mais particularmente: Chomsky foi um dos primeiros a formalizar uma hierarquia relacionando idiomas, gramáticas e autômatos. Esse insight ainda é muito relevante e é ministrado em todos os cursos de introdução à teoria dos autômatos. No entanto, a hierarquia específica que Chomsky criou e os nomes dos elementos da hierarquia não são mais significativos. Desde então, inventamos numerosos formalismos que se situam entre os níveis da hierarquia de Chomsky, acima ou abaixo dela. E os nomes que Chomsky usou não são particularmente interessantes, ou seja, não são baseados em uma medida interessante de complexidade ou qualquer coisa, são apenas números. As linguagens levemente sensíveis ao contexto devem ser do tipo 1.5 ou do tipo 1.7 ou do tipo 1.3? Quem se importa. "Ligeiramente sensível ao contexto" é um nome muito mais informativo.

O Zoológico de Complexidade é um pouco diferente porque está cheio de todos os tipos de equivalências condicionais e similares. Uma hierarquia mais moderna para a teoria dos autômatos não seria linear (por exemplo, compare CFG x PEG), mas ainda assim teria uma topologia conhecida. Para ter uma perspectiva da teoria moderna dos autômatos, você deve examinar o trabalho nas bibliotecas combinadoras do analisador e algumas coisas sobre a unificação e a teoria dos tipos (embora as duas se ramifiquem muito longe).

wren romano
fonte
4
Encontramos nomes melhores, sim. Isso não implica que os resultados estejam desatualizados.
Raphael
4
@Raphael: A desatualização não é por causa dos nomes, por si só, é porque a hierarquia específica introduzida por Chomsky não é mais usada. As inclusões descritas pela hierarquia de Chomsky ainda são (a) corretas e (b) entre as inclusões em qualquer hierarquia moderna; mas a hierarquia de Chomsky, como tal , não é terrivelmente relevante, exceto que atinge alguns dos pontos altos mais conhecidos. As pessoas não pesquisam mais a hierarquia de Chomsky, pesquisam em outros lugares. Não é como a torre polinomial que tem razões para seus nomes / estruturas.
Wren romano
26

Se alguma coisa no TCS está desatualizada, é essa hierarquia de inclusão do minúsculo subconjunto de classes de complexidade que passou a ser conhecido / considerado interessante em 1956.

Descanse em paz, Hierarquia de Chomsky, e você não deve mais assombrar o currículo da teoria da graduação.

Scott Aaronson
fonte
12
Como Juris Hartmanis uma vez gritou: "E as aulas de Chomsky? As aulas de Chomsky são uma abominação !!"
Ryan Williams
1
Ryan: Também me lembro de Juris chamando o CH de "abominação"! Enquanto escrevia minha resposta, eu estava debatendo se ele queria que seu comentário fosse publicado. Mas você o conhece melhor do que eu ... :-D
Scott Aaronson
Esse comentário também pode ser motivado, pelo menos um pouquinho, pela visão pejorativa de algumas ciências da computação e matemáticos em relação à linguística e outras ciências "fracas": xkcd.com/435 . Mas certamente a hierarquia de Chomsky hoje obscurece a visão da moderna teoria da complexidade, de modo que isso responde à minha pergunta. Ainda assim, seria bom ter uma substituição atualizada para começar no currículo da teoria da graduação, especialmente se você estiver mais interessado em linguagens e gramáticas formais para aplicações práticas.
Jakob
1
A Hierarquia de Chomsky lista classes de linguagens ordenadas pela complexidade da descrição, não pela complexidade da computação que geralmente está implícita quando você usa o termo "teoria da complexidade". Eles estão relacionados, obviamente. De qualquer forma, ainda não consigo entender como uma hierarquia (grosseira) pode obscurecer classes mais refinadas que dificilmente podem ser entendidas sem ter vindo da Hierarquia de Chomsky. Eles são a porta de entrada!
Raphael
20

Se você considerar a Hierarquia de Chomsky com nomes "modernos" (por exemplo, REG, LIN, CFL, CSL, RE ou DFA / NFA, PDA, LBA, TM), digo: Não, não está desatualizado!

Razão 0 : Ainda está correto no sentido de que suas definições e resultados não são contraditórios ao conhecimento mais recente.

Razão 1 : esses modelos de classes / computação ainda são os primeiros a serem ministrados - porque são simples e bem estudados. Tente ensinar o autômato de LR a um estudante de graduação sem primeiro cobrir o DFA / DPDA.

Razão 2 : As aulas ainda são os primeiros / principais parâmetros de referência para novas invenções (examinei um artigo sobre multi-CFGs que, é claro, dizia: mais que CFG, menos que CSG). Isso pode ser em parte porque eles são ensinados primeiro, mas também porque são simples e bem estudados.

Anti-Razão 3 : Os resultados não estão desatualizados apenas porque novas classes / modelos foram encontrados. Eles mantêm seu valor como básico do campo, apesar de não serem usados ​​ativamente na fronteira de pesquisa.

Rafael
fonte
10
"A matemática não envelhece , torna-se clássica ." (Eu não sei que esta citação é atribuída a, infelizmente.)
Heinrich Apfelmus
Você não quer dizer "NPDA" em vez de "DPDA"? Algumas linguagens livres de contexto são reconhecidas apenas por autômatos pushdown não-determinísticos.
Zsbán Ambrus
@ ZsbánAmbrus Muito bem; Eu deveria ter escrito apenas "PDA". Obrigado!
Raphael
O último motivo não é nada convincente (acho que é por isso que é um anti-motivo?). Muitos resultados ficam desatualizados porque são agrupados ou, às vezes, trivializados por uma abordagem diferente do assunto. Não estou dizendo isso aqui, apenas que o motivo, como afirmado, não diz muito. Além disso, um nitpick gramatical: "desatualizado" não é um verbo.
Sasho Nikolov
11

Eu acho que depende do modelo de computação. Se você considerar o finito / pushdown / etc. autômatos como modelo de computação, a hierarquia de Chomsky se torna importante (ver, por exemplo, o livro de Sipser). Por outro lado, desempenha pouco papel no modelo de computação de Turing.

A ilustração a seguir pode ser útil:

Editar: linguagens formais desempenham um papel importante no design de linguagens de computador (como Java) e compiladores, bem como no processamento de linguagem natural (PNL).

MS Dousti
fonte
Desculpe András, não consigo entender o seu comentário. O OP perguntou se a hierarquia de Chomsky está desatualizada. Seu raciocínio era que ele não o via no zoológico de complexidade etc. Eu respondi que, se ele considera os autômatos um modelo de computação, a hierarquia de Chomsky se torna relevante. Além disso, mencionei que as classes dessa hierarquia são importantes para o design do compilador e os algoritmos da PNL. IMHO, isso está totalmente relacionado à questão.
MS Dousti 17/10/10
2
Claro que a hierarquia de Chomsky não está realmente desatualizada, é encontrada na maioria das introduções da ciência da computação teórica, linguagens formais, design de compiladores etc. Acho que as linguagens de agradecimento entre REG e CFL e entre CFL também podem ser importantes. É apenas uma má idéia estender a hierarquia com esses idiomas porque a hierarquia de Chomsky tem um cheiro de "desatualizado" como não importante para a pesquisa atual?
Jakob
Não acho que seja uma má idéia, embora seja necessário encontrar algum aplicativo para o qual a nova extensão se encaixe.
MS Dousti 17/10/10