A resposta do @Victor Stafusa é excelente, venho aqui apenas aprofundar alguns pontos.
Linguagem
Uma linguagem é um subconjunto (podendo ser finito ou infinito) de palavras geradas pelo operador Estrela de Kleene sobre um conjunto de símbolos.
Palavra
Uma palavra é a concatenação de 0 ou mais símbolos.
Uma palavra com zero símbolos é a palavra vazia. Pode ser representada por epsilon ou por lambda, ou simplesmente por ""
.
Lambda:
Epsilon:
Um único símbolo é considerado uma palavra de tamanho 1. Dois símbolos concatenados é uma palavra de tamanho dois.
É possível concatenar qualquer palavra desejada, até mesmo a palavra vazia. Vou representar a concatenação com o operador ponto .
. Alguns exemplos de concatenação:
"a" . "b" -> "ab"
"ban" . "ana" -> "banana"
"" . "" -> ""
"" . "a" -> "a"
"a" . "" -> "a"
Formalmente, todo elemento formado pela estrela de Kleene sobre um conjunto de símbolos T
é uma palavra formada por T
.
Estrela de Kleene
Uma estrela de Kleene gera concatenações de palavras sobre um conjunto de palavras previamente existente.
Mas, Jefferson, você falou logo antes que uma linguagem é um subconjunto sobre do conjunto gerado pela Estrela de Kleene sobre símbolos, por que você está falando que a Estrela pode operar sobre palavras?
Lembra que mais faz pouco tempo que escrevi sobre palavras de tamanho 1? Bem, um único símbolo é uma palavra de tamanho um, então essas definições não entram em contradição.
O operador estrela de Kleene é sobre um conjunto V
é representado por V*
Uma palavra é gerada pela estrela de Kleene sobre V
se:
- ela for a palavra vazia;
- ela for uma palavra de
V
concatenada de uma palavra gerada por V*
.
Sim, a definição é recursiva. Mais formalmente, o segundo passo é dado pela seguinte expressão matemática:
Linguagem como conjunto
Linguagem L
é um subconjunto de T*
, sendo T
um conjunto de símbolos. Como conjunto, posso definir de várias maneiras. Por exemplo:
Essa é uma palavra formada pelos símbolos a
, b
e c
, de tal modo que todos os a
s apareçam antes de todos os b
, que por sua vez aparecem antes dos c
s. E também tem a mesma quantidade de a
s, b
s e c
s.
Para alguns casos, a linguagem precisa seguir uma estrutura, chamada de sintaxe. Para definir uma sintaxe, usa-se uma gramática. Infelizmente, a notação de conjunto é pobre para expressar a estrutura sintática de uma linguagem, então temos outra notação para isso...
Gramática derivativa
Gramática derivativa, ou gramática transformacional, foi proposta por Chomsky para se estudar de maneira estruturada como se formam frases em linguagem natural.
Uma gramática é definida como um conjunto de transformações de símbolos. Usualmente, temos que uma transformação é definida assim:
V -> W
Onde V
é uma forma léxica e W
outra forma léxica.
O que é uma forma léxica?
Vamos voltar um pouco para português, nossa língua. Uma versão reduzida da formação de frases seria:
- De modo geral, temos uma frase
F
F
pode ser descrita como SVO
, onde S
é um sujeito, V
é um sintagma adverbial e O
é um objeto
S
é descrito por um sintagma nominal Sn
- assim como
O
também é descrito como Sn
- Um
Sn
pode ser diretamente um nome N
, mas também pode ser um sintagma nominal combinado com um adjunto adnominal AN
antes ou depois de outro Sn
- Portanto, um
Sn
pode ser representado por N
, Sn . An
ou An . Sn
- Um
An
é um adjetivo Ad
que pode ser combinado por um advérbio Av
do mesmo jeito que um sintagma nominal é combinado com adjuntos adnominais
- Portanto,
An
pode ser representado por Ad
, An . Av
ou Av . An
- De modo semelhante, sintagmas verbais são verbos
Ve
ou combinações de sintagmas verbais e advérbios: V
é representado por Ve
, V . Av
ou Av . V
N
é a união das classes morfológicas dos substantivos Su
e pronomes P
Su
, P
, Ve
, Ad
e Av
são as classes gramaticais que estudamos na escola
Eu posso transformar essas regras em uma gramática da seguinte forma:
F -> SVO
S -> Sn
O -> Sn
Sn -> N | An Sn | Sn An
N -> Su | P
An -> Ad | Av An | An Av
V -> Ve | Av V | V Av
Uma forma léxica é qualquer concatenação de símbolos, podendo conter símbolos intermediários e finais em quaisquer proporções. Exemplos de forma léxica:
F
"verde"
Sn
"incolores" . "ideias" . "verdes"
Sn . V . Sn
"incolores" . Sn . Ad
"gato" . "amarelas"
Uma palavra é uma forma léxica especial que é composta apenas de símbolos finais. Portanto, dos exemplos acima, apenas os seguintes são palavras:
"verde"
"incolores" . "ideias" . "verdes"
"gato" . "amarelas"
Note que a estrutura gramatical não precisa fazer com que a palavra gerada faça sentido na linguagem usada, pois não há avaliação semântica, apenas sintática. Um exemplo de coisa sem sentido é ter algo ("ideias") que tem uma cor ("verdes") e não tem cor alguma ("incolores").
A língua gerada por uma gramática é o conjunto de todas as possíveis palavras que é possível gerar com a gramática partindo de um símbolo inicial; essa linguagem é indicada como L(G)
.
Classificação de gramáticas
Como o Victor Safusa já falou, existem diversos tipos de gramáticas. Elas são diferenciadas em como cada produção é feita.
Uma gramática sensível ao contexto tem a seguinte forma:
A V B -> A W B
A B -> B A
V -> Z
Note que V
se transformou em W
dado o contexto A
prefixo e B
sufixado. Em contraponto, note que V
virar Z
não tem nenhum contexto envolvido. A produção V -> Z
é dita, portanto, livre de contexto.
Uma gramática livre de contexto é uma gramática cujas produções são todas livres de contexto. Para ser livre de contexto, o lado esquerdo (produtor?) só pode ter um único símbolo não terminal, sendo livre o lado direito (produzido?).
Como curiosidade, uma gramática regular segue a seguinte forma, para V
e W
símbolos não terminais e a
um símbolo terminal qualquer:
V -> a W
V -> a
V ->
No capítulo 7 da minha Monografia de Graduação, usei Gramáticas Sensíveis a contexto para demonstrar algumas propriedades simulações de redes de Petri.
Linguagens livres de contexto
Uma linguagem é livre de contexto se é possível descrever ela por uma gramática livre de contexto. Simples assim, não é?
Pois bem, então para ela não ser livre de contexto, é preciso demonstrar que não é possível construir a linguagem, mesmo com todas as infinitas produções possíveis.
Para uma gramática ser infinita, uma coisa precisa ser verdade: um símbolo não terminal precisa produzir a si mesmo. De modo grosseiro, seria algo assim (sempre fazendo a geração da palavra a partir do símbolo entre parênteses):
S -> A(B)C -> AXT(Z)LC -> ... -> AXTPQO S AHFUQLC
Do símbolo S
, alcancei S
novamente, antecedido por AXTPQO
e sucedido por AHFUQLC
. Isso significa que eu também posso obter a expressão lexical AXTPQO AXTPQO S AHFUQLC AHFUQLC
, e também a AXTPQO AXTPQO AXTPQO S AHFUQLC AHFUQLC AHFUQLC
, e genericamente (AXTPQO)^n S (AHFUQLC)^n
. Essa operação (sair de S
e chegar em S
novamente) é chamada de bombeamento.
Visualmente, tem essa imagem do lema do bombeamento na Wikipedia que mostra a generalização do parágrafo anterior (N
bombeia N
):
Toda linguagem livre de contexto segue esse lema do bombeamento quando infinitas.
EDIT Um nome alternativo que se dá a essa produção de bombeamento é auto aninhamento; N
está aninhado dentro das produções de N
Respostas diretas
O que é uma linguagem livre de contexto?
Uma linguagem gerada por uma gramática livre de contexto.
Como é possível, se é possível, definir se uma linguagem é livre de contexto ou não?
De modo geral, basta provar escrevendo uma gramática livre de contexto, mas nem sempre essa tarefa é trivial.
Existem casos em que é impossível saber se uma linguagem sensível ao contexto é livre de contexto. Até mesmo provar que uma linguagem não é livre de contexto é difícil, pois até mesmo linguagens que respeitam o lema do bombeamento podem não ser livres de contexto.