Diferença entre gramática regular e gramática Context-Free

O linguista Noam Chomsky desenvolveu as noções de livre de contexto e regulares gramáticas em seu 1959 trabalho "em certas propriedades formais de gramáticas." Ele postulou a existência de vários tipos de gramática básicas, que diferem umas das outras em termos de complexidade das expressões linguísticas que eles podem produzir. gramáticas regulares são mais simples e menos produtivas do que gramáticas livres de contexto.

gramáticas regulares e livres de contexto diferem nos tipos de regras que permitem. As regras de gramáticas livres de contexto permitem possíveis frases como combinações de palavras individuais não relacionados (que Chomsky chama de "terminais") e grupos de palavras (frases, ou o que Chomsky chama "não-terminais"). gramáticas livres de contexto permitem que palavras e frases individuais em qualquer ordem e permitir frases com qualquer número de palavras e frases individuais. gramática regular, por outro lado, permitir que somente palavras individuais, juntamente com uma única frase por frase. Além disso, frases em gramática regular deve aparecer na mesma posição em cada frase ou expressão, gerada pela gramática.

Porque gramáticas livres de contexto permitem uma ampla gama de regras do que gramática regular, eles podem gerar uma ampla gama de estruturas que gramáticas regulares. Por exemplo, eles podem envolver várias estruturas possíveis de frases, como "uma garota da cidade com problemas de dinheiro" (aqui, as estruturas irá variar dependendo se "com problemas de dinheiro" descreve a cidade ou a menina). gramática regular não pode fazer this.Rather, eles podem gerar apenas expressões simples que consistem em cordas de, palavras estruturalmente independentes individuais e, possivelmente, uma única frase maior (como "pessoas muito, muito inteligentes").

gramáticas livres de contexto são usados ​​em processamento de linguagem natural para gerar e analisar dados de linguagem, porque eles podem capturar muitas das características que definem a linguagem humana, tais como o seu potencial para estruturas infinitamente recursiva. gramática regular, que geram apenas um subconjunto das expressões de gramáticas livres de contexto, também são usados ​​para processamento de linguagem natural. No entanto, eles só podem replicar ou processo curto e gramaticalmente simples expressões linguísticas, tais como expressões curtas normalmente encontrados em diálogo informal.