O que é uma gramática livre de contexto?

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.

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".

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.