O que é uma gramática livre de contexto?

104

Alguém pode me explicar o que é uma gramática livre de contexto? Depois de olhar a entrada da Wikipedia e depois a entrada da Wikipedia sobre gramática formal, fico total e totalmente confuso. Alguém poderia ser gentil em explicar o que são essas coisas?

Estou me perguntando isso porque desejo investigar a análise, e também paralelamente, a limitação de um mecanismo de regex.

Não tenho certeza se esses termos estão diretamente relacionados à programação ou se estão mais relacionados à linguística em geral. Se for esse o caso, peço desculpas, talvez isso possa ser movido se for o caso.

Ell
fonte
2
Está mais relacionado aAutomata Theorem
Rahul
2
Se você estiver interessado em linguagens formais e teoria de autômatos para análise, sugiro um livro como Linguagens e Máquinas de Sudkamp ou Compiladores de Aho, Sethi & Ullman . Cada livro fornece uma descrição formal de uma gramática livre de contexto, que é um tipo de gramática formal, então afirma e prova teoremas básicos sobre gramáticas livres de contexto necessárias para entendê-los (como o lema do bombeamento para linguagens livres de contexto e conversão e teoremas da forma normal). Não há pré-requisito matemático para aprender a teoria da linguagem formal além de uma compreensão superficial da teoria dos conjuntos.
danportin
1
Essas questões não deveriam ser migradas para a Ciência da Computação Teórica?
Pale Blue Dot

Respostas:

110

Uma gramática livre de contexto é uma gramática que satisfaz certas propriedades. Na ciência da computação, as gramáticas descrevem linguagens; especificamente, eles descrevem linguagens formais.

Uma linguagem formal é apenas um conjunto (termo matemático para uma coleção de objetos) de strings (sequências de símbolos ... muito semelhante ao uso de programação da palavra "string"). Um exemplo simples de linguagem formal é o conjunto de todas as sequências binárias de comprimento três, {000, 001, 010, 011, 100, 101, 110, 111}.

As gramáticas funcionam definindo as transformações que você pode fazer para construir uma string na linguagem descrita por uma gramática. As gramáticas dirão como transformar um símbolo inicial (geralmente S) em uma sequência de símbolos. Uma gramática para o idioma fornecido antes é:

S -> BBB
B -> 0
B -> 1

A maneira de interpretar isso é dizer que Spode ser substituído por BBB, e Bpode ser substituído por 0, e Bpode ser substituído por 1. Portanto, para construir a string 010, podemos fazer S -> BBB -> 0BB -> 01B -> 010.

Uma gramática livre de contexto é simplesmente uma gramática em que o que você está substituindo (à esquerda da seta) é um único símbolo "não terminal". Um símbolo não terminal é qualquer símbolo que você usa na gramática e que não pode aparecer em suas strings finais. Na gramática acima, "S" e "B" são símbolos não terminais, e "0" e "1" são símbolos "terminais". Gramáticas como

S -> AB
AB -> 1
A -> AA
B -> 0

Não são regulares, pois contêm regras como "AB -> 1".

aegrisomnia
fonte
12
Por 'não regular', você quer dizer 'não livre de contexto'? (porque a linguagem representável por CFGs é um superconjunto daquelas representáveis ​​por expressões regulares)
Anti Terra
3
Deve "S pode ser substituído por B" ler "S pode ser substituído por BBB"?
Cosmo Harrigan
4
Meu Deus, esta é uma das respostas mais bem explicadas que já vi no SO.
Rafael Dias da Silva
1
@AntiEarth o segundo exemplo não é uma gramática regular porque tem regras que geram dois símbolos não terminais a partir de um único símbolo não terminal, o que não é permitido em gramáticas regulares (também, como OP apontou, ele tem regras com vários símbolos não terminais em a esquerda). en.wikipedia.org/wiki/Regular_grammar
awwsmm
21

A Teoria da Linguagem está relacionada à Teoria da Computação. Qual é o lado mais filosófico da Ciência da Computação, sobre decidir quais programas são possíveis, ou quais serão possíveis de escrever, e que tipo de problemas é impossível escrever um algoritmo para resolver.

Uma expressão regular é uma maneira de descrever uma linguagem regular. Uma linguagem regular é uma linguagem que pode ser decidida por um autômato finito determinístico.

Você deve ler o artigo sobre máquinas de estado finito: http://en.wikipedia.org/wiki/Finite_state_machine

E linguagens regulares: http://en.wikipedia.org/wiki/Regular_language

Todas as linguagens regulares são linguagens livres de contexto, mas há linguagens livres de contexto que não são regulares. Uma Context Free Language é o conjunto de todas as strings aceitas por uma Context Free Grammer ou um Pushdown Automata que é uma máquina de estados finitos com uma única pilha: http://en.wikipedia.org/wiki/Pushdown_automaton#PDA_and_Context-free_Languages

Existem linguagens mais complicadas que requerem uma Máquina de Turing (qualquer programa possível que você possa escrever no seu computador) para decidir se uma string está ou não na linguagem.

A teoria da linguagem também está muito relacionada ao problema P vs. NP e algumas outras coisas interessantes.

Meu livro de texto do terceiro ano de Introdução à Ciência da Computação foi muito bom em explicar essas coisas: Introdução à Teoria da Computação. Por Michael Sipser. Mas me custou cerca de US $ 160 para comprá-lo novo e não é muito grande. Talvez você possa encontrar uma cópia usada ou encontrar uma cópia em uma biblioteca ou algo que possa ajudá-lo.

EDITAR:

As limitações das expressões regulares e das classes superiores de idioma têm sido pesquisadas muito nos últimos 50 anos ou mais. Você pode estar interessado no lema do bombeamento para linguagens regulares. É um meio de provar que um determinado idioma não é regular:

http://en.wikipedia.org/wiki/Pumping_lemma_for_regular_languages

Se uma linguagem não é regular, pode ser Context Free, o que significa que pode ser descrita por um Context Free Grammer, ou pode ser até mesmo em uma classe de linguagem superior, você poderia provar que não é Context Free pelo lema de bombeamento para Context Free linguagens que é semelhante ao das expressões regulares.

Uma linguagem pode até ser indecidível, o que significa que até mesmo uma máquina de Turing (pode programar seu computador pode ser executado) não pode ser programada para decidir se uma string deve ser aceita como na linguagem ou rejeitada.

Acho que a parte em que você está mais interessado são as Máquinas de Estados Finitos (Determinísticas e Determinísticas) para ver quais linguagens uma Expressão Regular pode decidir, e o lema do bombeamento para provar quais linguagens não são regulares.

Basicamente, uma linguagem não é regular se precisar de algum tipo de memória ou habilidade para contar. A linguagem dos parênteses correspondentes não é regular, por exemplo, porque a máquina precisa se lembrar se abriu um parêntese para saber se deve fechar um.

A linguagem de todas as strings que usam as letras aeb que contêm pelo menos três b's é uma linguagem normal: a ba ba ba

A linguagem de todas as strings que usam as letras aeb que contêm mais b's do que a's não é regular.

Além disso, você não deve dizer que todas as linguagens finitas são regulares, por exemplo:

A linguagem de todas as strings com menos de 50 caracteres usando as letras aeb que contêm mais b's do que a's é regular, já que é finita, sabemos que pode ser descrita como (b | abb | bab | bba | aabbb | ababb |. ..) ect até que todas as combinações possíveis sejam listadas.

Paulo
fonte
1
Expressões regulares não são programas de decisão que combinam strings com padrões. São expressões que denotam conjuntos regulares, para os quais o problema de associação é decidível.
danportin
1
Se um conjunto for regular, é obviamente decidível. Não tenho certeza de como expressar isso. Eles são efetivamente programas de decisão que não têm memória.
Paul
Você está descrevendo autômatos finitos determinísticos, que fornecem um procedimento de decisão para linguagens regulares ("programas de decisão que não têm memória"). Expressões regulares são termos que denotam linguagens regulares, e não programas são procedimentos. Esta foi a minha única reclamação.
danportin
1
Eu mudei para "Uma expressão regular é uma maneira de descrever uma linguagem regular. Uma linguagem regular é uma linguagem que pode ser decidida por um autômato finito determinístico." Isso soa melhor?
Paul