33

No Wikipédia possui a seguinte afirmação:

Na teoria de linguagens formais, uma linguagem livre de contexto (LLC) é uma linguagem gerada por alguma gramática livre de contexto (GLC). Diferentes gramáticas livres de contexto podem gerar a mesma linguagem livre de contexto, ou, inversamente, uma dada linguagem livre de contexto pode ser gerada por diferentes gramáticas livres de contexto.

Oh God!!!

No entanto, achei a explicação um pouco confusa, embaralhada, e sendo assim ainda pergunto:

  • O que é uma linguagem livre de contexto?
  • Como é possível, se é possível, definir se uma linguagem é livre de contexto ou não?
2
  • Fala a respeito das linguagens de programação?
    – gato
    Commented 30/01/2017 às 19:17
  • 1
    @gato linguagens de programação e compiladores.
    – viana
    Commented 30/01/2017 às 19:19

2 Respostas 2

30
+500

Existe uma hierarquia definida por Chomsky e refinada por outros pesquisadores acerca de estrutura de linguagens denotadas por sequências de símbolos, palavras, letras, etc. Essa estrutura contém os seguintes níveis:

  1. Linguagens finitas.

  2. Linguagens regulares - aquelas das expressões regulares.

  3. Linguagens livres de contexto - vou explicar abaixo.

  4. Linguagens sensíveis ao contexto.

  5. Linguagens recursivas (também denominadas decidíveis).

  6. Linguagens recursivamente enumeráveis (também denominadas semi-decidíveis).

  7. Linguagens irrestritas - ou seja, esta é a categoria mais geral que engloba todas e quaisquer linguagens.

Cada nível é um superconjunto do nível anterior. Assim sendo:

  • As linguagens livres de contexto são mais poderosas e mais gerais do que as linguagens regulares. Ou seja, com linguagens livres de contexto você pode expressar estruturas/linguagens que não podem ser representadas por expressões regulares.

  • Todas as linguagens que podem ser expressas por meio de uma expressão regular também podem ser expressas por meio de uma linguagem livre de contexto.

  • As linguagens livres de contexto ainda estão bem longe de serem linguagens capazes de expressar qualquer coisa. Existem alguns níveis acima delas.

A hierarquia fica assim:

hierarquia

Bem, vamos dar uma olhada em expressões regulares primeiro já que é mais provável que você já as tenha visto antes. Por exemplo, uma expressão regular do tipo ab(c*)(d|e)[f](g+) denota sequências de símbolos que tenham a seguinte estrutura:

  1. Comecem por ab.

  2. Tenham zero ou mais cs em seguida.

  3. Tenham um d ou um e em seguida.

  4. Depois, podem ou não ter um f.

  5. Terminem com um ou mais gs.

Pois bem, vemos que expressões regulares podem conter regras nos seguintes formatos:

  • Sequências de símbolos da cadeia de entrada.

  • Repetição zero ou mais vezes de subexpressões.

  • Repetição uma ou mais vezes de subexpressões.

  • Escolha entre duas ou mais subexpressões.

  • Subexpressões opcionais (aparecem zero ou uma vezes).

Entretanto, uma expressão regular não é recursiva. Já uma gramática livre de contexto é uma gramática composta por regras recursivas denominadas produções. Cada produção é identificada por um símbolo/nome chamado de não-terminal. Um dos símbolos não-terminais é denominado de símbolo inicial, que é o ponto de partida no caso de geração e o objetivo final no caso de aceitação (mais abaixo explico melhor isso). Além dos símbolos não-terminais, temos os símbolos terminais que correspondem a símbolos (caracteres) que estão representados diretamente na cadeia de entrada.

As gramáticas livres de contexto podem conter todos esses elementos que as expressões regulares têm, mas elas tem uma possibilidade a mais. Elas podem também:

  • Expandir símbolos não-terminais em meio aos terminais, inclusive símbolos não-terminais que se expandam de forma recursiva.

Para demonstrar, vou pegar como exemplo uma das gramáticas que está no artigo da wikipedia:

T → x
T → y
T → z
S → S + T
S → S - T
S → S * T
S → S / T
T → ( S )
S → T

Uma forma equivalente a essa gramática seria essa:

T → x | y | z | ( S )
S → S + T | S - T | S * T | S / T | T

Nesta gramática, os símbolos x, y, z, +, -, *, /, ( e ) são os terminais e os símbolos S e T são os não-terminais. O símbolo não-terminal S é o símbolo inicial. Esta gramática modela expressões aritméticas (embora não tenha regras de precedência).

A setinha → é lida como "deriva" ou "produz". Assim sendo, a regra T → x pode ser lida como "T deriva x", ou "T produz x". Observe que neste exemplo dado, é possível que um S derive um outro S ou que um T derive um outro T de forma direta ou indireta, pois as produções são aplicadas de forma recursiva.

Para ver um exemplo na prática, observe que uma expressão tal como x-(z)+(x*x) pode ser produzida a partir do símbolo inicial S assim:

S           // Símbolo inicial
S+T         // Aplicação da regra S -> S + T
S+(S)       // Aplicação da regra T -> ( S )
S+(S*T)     // Aplicação da regra S -> S * T
S+(T*T)     // Aplicação da regra S -> T
S+(T*x)     // Aplicação da regra T -> x
S+(x*x)     // Aplicação da regra T -> x
S-T+(x*x)   // Aplicação da regra S -> S - T
S-(S)+(x*x) // Aplicação da regra T -> ( S )
S-(T)+(x*x) // Aplicação da regra S -> T
S-(z)+(x*x) // Aplicação da regra T -> z
T-(z)+(x*x) // Aplicação da regra S -> T
x-(z)+(x*x) // Aplicação da regra T -> x

O processo de reconhecimento é o inverso:

x-(z)+(x*x) // Cadeia de entrada
T-(z)+(x*x) // Aplicação da regra T -> x
S-(z)+(x*x) // Aplicação da regra S -> T
S-(T)+(x*x) // Aplicação da regra T -> z
S-(S)+(x*x) // Aplicação da regra S -> T
S-T+(x*x)   // Aplicação da regra T -> (S)
S+(x*x)     // Aplicação da regra S -> S - T
S+(T*x)     // Aplicação da regra T -> x
S+(T*T)     // Aplicação da regra T -> x
S+(S*T)     // Aplicação da regra S -> T
S+(S)       // Aplicação da regra S -> S * T
S+T         // Aplicação da regra T -> (S)
S           // Aplicação da regra S -> S + T

Note que o processo de gerar ou produzir uma cadeia de caracteres é aquele que, partindo do símbolo inicial, chega-se a uma sequência de terminais, enquanto que o processo de reconhecer ou aceitar uma cadeia de caracteres é aquele que partindo-se da cadeia de caracteres, chega-se ao símbolo inicial. Estes processos de geração e reconhecimento também existem para as expressões regulares, pois posso usá-las tanto para gerar como para reconhecer cadeias de caracteres.

Agora, observe que no caso do exemplo acima, a expressão gerada e/ou reconhecida sempre terá os parênteses balanceados e adequadamente aninhados, coisa que expressões regulares não são capazes de fazer. Isso demonstra que gramáticas livres de contexto são mais poderosas/expressivas que expressões regulares.

Quanto a diferença entre linguagens livres de contexto e gramáticas livres de contexto é que uma gramática é aquilo que postei acima, um conjunto de regras. Por outro lado, uma linguagem é um determinado conjunto de cadeias de símbolos que são aceitas ou geradas, independente de quais são as regras usadas para gerá-las ou aceitá-las. Uma linguagem que pode ser gerada ou aceita por uma gramática livre de contexto é uma linguagem livre de contexto. Uma mesma linguagem pode ser gerada ou reconhecida por diferentes gramáticas, que neste caso são equivalentes.

Talvez você esteja se perguntando porquê esse nome "livre de contexto". A resposta é que o reconhecimento de uma subexpressão não depende do contexto onde ela está inserida. Ou seja, não depende daquilo que antecede ou sucede tal subexpressão. Por exemplo, uma (sub)expressão x-y pode ser reconhecida ou gerada como um S na gramática anterior independente do que venha antes ou depois desse x-y. Já em linguagens sensíveis ao contexto (ou que estejam ainda mais além na hierarquia) isso pode não ser verdade.

Por fim, para se definir se uma linguagem é livre de contexto, você deve demonstrar que existe alguma gramática livre de contexto que a reconheça. Para provar que ela não é livre de contexto, deve provar que não existe gramática livre de contexto que a reconheça.

0
14

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: lambda

Epsilon: 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:

  1. ela for a palavra vazia;
  2. 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:

formação recursiva de palavras sobre V

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:

palavra com mesma quantidade de 'a', 'b' e 'c'

Essa é uma palavra formada pelos símbolos a, b e c, de tal modo que todos os as apareçam antes de todos os b, que por sua vez aparecem antes dos cs. E também tem a mesma quantidade de as, bs e cs.

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:

  1. De modo geral, temos uma frase F
  2. F pode ser descrita como SVO, onde S é um sujeito, V é um sintagma adverbial e O é um objeto
  3. S é descrito por um sintagma nominal Sn
  4. assim como O também é descrito como Sn
  5. 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
  6. Portanto, um Sn pode ser representado por N, Sn . An ou An . Sn
  7. 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
  8. Portanto, An pode ser representado por Ad, An . Av ou Av . An
  9. 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
  10. N é a união das classes morfológicas dos substantivos Su e pronomes P
  11. 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 Se 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):

lema do bombeamento, N bombeando 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.

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .