Aula 02 – Teoria da Computação

Conceitos básicos de linguagens

Nesta aula vamos entrar no conteúdo mais específico de linguagens formais e autômatos, como: alfabetos, palavras, cadeias e linguagens.

Podemos definir uma linguagem como a expressão de ideias, usando símbolos (sejam eles escritos, orais, ou de outro tipo) que se agrupam segundo determinadas regras. Assim, uma linguagem tem aspectos léxicos (relacionados aos símbolos usados), sintáticos (relacionados às regras) e semânticos (relacionados ao significado).  O objetivo desta parte é nos aprofundarmos no aspecto sintático, em particular no problema da análise sintática, suas soluções para diferentes tipos de gramáticas, bem como as consequências destas soluções. Neste curso não será abordado o aspecto semântico de uma linguagem.

Mesmo sem considerar o aspecto semântico, os aspectos léxico e sintático de uma linguagem são bastante complexos. Em nossa primeira definição consideramos apenas o aspecto léxico. Dado um conjunto finito de símbolos, comumente chamado alfabeto, uma linguagem sobre esse alfabeto é um conjunto de sequências finitas de símbolos deste alfabeto. Vamos definir esses conceitos de forma mais cadenciada.

“Um alfabeto (chamado também de vocabulário) é um conjunto finito não vazio de símbolos.”

A definição de alfabeto, bem como outras definições apresentadas aqui, pode ser encontrada em referências clássicas como: (MENEZES, 2000) e (HOPCROFT; MOTWANI; ULLMAN, 2002).

O alfabeto latino moderno é o seguinte conjunto de 26 símbolos: {A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z}. É comum representarmos o alfabeto pela letra Σ . Outros exemplos de alfabeto são:

• Σ 1 = { α, β, γ, δ, …, ω }
• Σ 2 = { 0, 1 }

Com o primeiro você pode escrever palavras gregas e com o segundo você pode escrever palavras binárias (números na base 2).

“Uma cadeia de símbolos de um dado alfabeto (também chamada de string, palavra ou sentença) é uma sequência finita de símbolos deste alfabeto.”

Para o alfabeto Σ 1 = { α, β, γ, δ, …, ω }  podemos escrever a cadeia ” ψω “.

Para o alfabeto Σ 2 = { 0, 1 } podemos escrever a cadeia “10001”.

A cadeia formada por uma sequência com nenhum símbolo é conhecida como a cadeia vazia. Representamos a cadeia vazia com o símbolo ε . Note que a cadeia vazia é uma cadeia, ou palavra, sobre qualquer alfabeto. Cadeias de símbolos, ou palavras, sendo sempre uma sequência finita de símbolos, possuem comprimento (cardinalidade), que é a quantidade de símbolos que ocorrem na mesma.

Qualquer cadeia de símbolos tem um comprimento. Por exemplo, a cadeia “10001” tem comprimento 5. A cadeia vazia é normalmente representada em linguagens de programação como “”.

Uma operação rotineira quando lidamos com material escrito é a justaposição de palavras de uma linguagem, produzindo novas palavras. Esta justaposição é uma operação tão básica que ela prescinde de uma possível gramática. Isto quer dizer que a operação de justaposição, ou de concatenação de palavras, pode ser realizada entre quaisquer palavras da linguagem. Em português não é qualquer justaposição de palavras que pode ser considerada uma palavra da língua portuguesa. Nossa definição de linguagem não pressupõe que esta tenha que ter gramática. Mais à frente veremos exemplos de linguagens que não possuem gramática. Assim, a operação de concatenação é tomada como sendo sempre definida para quaisquer duas palavras.

“Dadas duas cadeias, definimos sua concatenação como a justaposição de seus valores. Por exemplo, se ω₁ =”101″ e ω₂ =”000″, sua concatenação é “101000”. Representamos a concatenação como ω₁ ° ω₂ ou simplesmente ω₁ ω₂ .”

Considere 3 cadeias ω₁, ω₂ e ω₃ . Se formarmos a concatenação de ω₁ com ω₂ e depois concatenarmos ω₃ teremos a justaposição das 3 palavras como o resultado destas operações, a saber ω₁ ω₂ ω₃. Isso é o mesmo que concatenar ω₂ e ω₃ e fazer em seguida a concatenação de ω₁ ou resultado anterior. Em termos matemáticos, dizemos que a concatenação é um operador associativo, isto é, ω₁°(ω₂°ω₃)=(ω₁°ω₂)°ω₃. A cadeia vazia também pode ser concatenada.

No entanto, prefixos de uma cadeia são as subsequências de símbolos do início da cadeia.

Dadas duas cadeias, ω₁ e ω₂, dizemos que ω₁ é prefixo de ω₂ se existe uma cadeia ω₁ tal que ω₁°ω₃=ω₂ .

A cadeia “101” possui os seguintes prefixos: ε, “1”, “10” e “101”. (Explique.)

Os sufixos de uma cadeia são definidos de forma análoga, porém tomando as subsequências do final da cadeia. Deixamos a definição como exercício para o leitor. A cadeia “100” possui os seguintes sufixos: ε, “0”, “00” e “100”.

Finalmente podemos apresentar a definição de linguagens.

“Dado um alfabeto definimos uma linguagem sobre este alfabeto como um conjunto de cadeias sobre este alfabeto.”

Para o alfabeto Σ₂ = { 0, 1 } temos infinitas linguagens possíveis, entre elas:

• L₁=Ø
• L₂={ε}
• L₃={Ø, 0, 1, 00, 01, 10, 11, 000, …}

A primeira linguagem não possui cadeia. A segunda linguagem possui apenas a cadeia vazia, enquanto a última possui todas as cadeias possíveis com símbolos do alfabeto Σ₂.

Sabemos que podemos concatenar duas cadeias. Esta operação pode ser estendida para uma linguagem. Definimos a concatenação de duas linguagens como a linguagem cujas cadeias são todas as possíveis concatenações entre cadeias da primeira linguagem com cadeias da segunda linguagem.

Dadas as linguagens L₁ e L₂, definimos sua concatenação como a linguagem L₁°L₂={ω₁°ω₂|ω₁∈L₁ e ω₂∈L₂}.

Quando repetimos a operação de concatenação com a mesma linguagem usamos a notação de potência. Por exemplo, L₁²=L₁°L₁ e L₁³=L₁°L₁°L₁.

Definimos L⁰ = ∅ e L^{n + 1}=Lⁿ °L .

Se fizermos a união de todas as potências de L, de L⁰ em diante, obtemos o fecho de Kleene da linguagem L, representado por L^*.

Definimos L^*=ε∪L⁰∪L¹∪L²∪…

Para o alfabeto L={0, 1} temos:

L^*={ε, 0, 1, 00, 01, 10, 11, 000, …}

Se L é uma linguagem, então L* é o menor subconjunto de L que contém ε (denominado cadeia vazia) e é fechado numa operação de concatenação. Esse conjunto também pode ser descrito como o conjunto de todos elementos que podem ser formados através da concatenação de zero ou mais elementos de V.

Se L é um alfabeto, então L* é o conjunto de todas as cadeias finitas de símbolos de L, incluindo a cadeia vazia.

Usando a concatenação de conjuntos, a união e o fecho de Kleene, podemos especificar algumas linguagens simples.

Exemplos do fecho de Kleene aplicado a uma linguagem:

Exemplo do fecho de Kleene aplicado a um alfabeto:

Considerando o alfabeto Σ = {0, 1} podemos especificar algumas linguagens formadas por cadeias que representam números na base binária de numeração.

• L={números na base 2 que são múltiplos de 4 (terminam com 00)} = {0, 1}°{ 00}
• L={todos os números na base 2, sem permitir 0’s desnecessários à esquerda}=({1}°{0, 1}^*)∪{0}
• L = {todos os números na base 2, que têm um número ímpar de bits ligados (número ímpar de caracteres 1)} ={0}^*º{1}º{0}^*º{1}^*{0}^*º{1}º{0}^*

Uma variação do fecho de Kleene é usar o símbolo +. Definimos L⁺ = L¹∪L²∪L³∪…

Podemos definir o operador * usando o operador + e vice-versa.  Podemos definir L^* como a união de L⁰ com L⁺, enquanto que L⁺, por sua vez, pode ser definida como L⁺ = L° L^*.

Então:

• L⁺=L^*-{ε}

Precedência dos operadores nas expressões regulares:

Exemplo:

A expressão regular (ab|c^∗) = ((ab)|c^∗) = ((ab)|(c^∗)) representa o conjunto {ab,ε,c,cc,ccc…}. A expressão regular a(b|c)^∗representa o conjunto {a, ab, ac,abc, abb, acc, …}. Finalmente, (ab|c)^∗ representa o conjunto {ε, ab, c, abc, cab,abab, cc, …}.

Considerem-se o alfabeto Σ = {a,b,c,d} e os dois subconjuntos A = {a}, B = {b,c}.  A seguir são apresentadas diferentes linguagens sobre Σ, definidas através da notação dos conjuntos e das expresões regulares:

• Sentenças que possuem no mínimo um símbolo a: Σ^∗AΣ^∗ ou (a|b|c|d)^∗a(a|b|c|d)^∗
• Sentenças que possuem exatamente dois símbolos a: (Σ−A)^∗A(Σ−A)^∗A(Σ−A)^∗ ou (b|c|d)^∗a(b|c|d)^∗a(b|c|d)^∗
• Sentenças que possuem um número par de símbolos a: ((Σ−A)^∗A(Σ−A)^∗A(Σ−A)^∗)^∗ ou ((b|c|d)^∗a(b|c|d)^∗a(b|c|d)^∗)^∗
• Sentenças que são iniciadas com o símbolo a e terminam com o símbolo b ou c: AΣ^∗B ou a(a|b|c|d)^∗(b|c)
• Sentenças contendo apenas os símbolos a,b,c, com no mínimo um símbolo: (A∪B)⁺ou (a|b|c)⁺
• Sentenças formadas por símbolos do alfabeto {a,b,c,d} contendo uma (e somente uma) subcadeia constituída por um símbolo do conjunto A e dois (e somente dois) do conjunto B, nesta ordem: ((Σ−A)−B)^∗ABB((Σ−A)−B)^∗ ou d^∗a(b | c)(b | c)d^*

 

Considere agora a seguinte linguagem:

• L={00, 000, 00000, 0000000, …}.

Esse é um exemplo de linguagem infinita onde a listagem de alguns poucos elementos da mesma não deixa claro o que queremos especificar. Neste caso queremos listar as cadeias que possuem apenas o símbolo “0”, repetido uma quantidade p de vezes, sendo p um número primo. Como fazer para especificar de forma finita uma linguagem infinita? Uma possibilidade é fazer um programa de computador para listar todos os elementos da linguagem. Será que isto é sempre possível?

Vamos pensar no alfabeto Σ = {n, +, ×} . Vamos entender n como representando um número qualquer, + como a soma, e × como a multiplicação. Queremos definir uma linguagem L sobre Σ como sendo a linguagem de todas as ‘expressões’ bem formadas usando-se essas duas operações:

L = {n, n + n, n × n, n + n + n, n + n × n, n × n + n, n × n × n, …}

Neste momento, temos uma definição de linguagem que diz que a linguagem é simplesmente um conjunto de sentenças (cadeias).  Isso ignora totalmente o aspecto estrutural da linguagem. Na próxima parte vamos introduzir o conceito de gramática e de linguagem gerada por uma dada gramática, com isso, vamos estar especificando a sintaxe destas linguagens e, ao mesmo tempo, apresentando uma forma de especificar finitamente linguagens infinitas.

Linguagens formais e gramáticas

Nesta parte, você verá os conceitos de gramática, derivação e linguagem gerada por uma gramática. Estes conceitos completam os conceitos vistos na seção anterior, permitindo a formalização de sintaxe de uma linguagem. Com estes conceitos será formulado o problema da análise sintática: dada uma cadeia e uma gramática, a cadeia está na linguagem gerada por esta gramática? Trata-se
de um problema difícil, vamos passar a maior parte do restante do curso investigando a solução deste problema para diversos tipos de gramáticas, com um nível de complexidade crescente. Esses diferentes tipos de gramáticas serão vistos ainda nesta seção, quando abordarmos a Hierarquia de Chomsky.

O conceito de linguagem apresentado anteriormente deixa a desejar, por não abordar o aspecto sintático de uma linguagem. Além disso, observamos que as linguagens mais interessantes para o nosso estudo são infinitas, e temos alguma dificuldade para especificar algumas destas linguagens de forma precisa. Nesta seção, vamos apresentar o conceito de gramática. Gramáticas compõem uma forma de especificar linguagens, podendo especificar linguagens infinitas. Além disso, gramáticas mostram como cada cadeia de uma linguagem é gerada através de regras, o que modela o aspecto sintático da linguagem.

Como um primeiro exemplo de gramática, suponha que estamos interessados em especificar a linguagem L_D dos números, numerais para sermos mais precisos, não negativos na base decimal. Estamos interessados não só nos inteiros, como também nos números com ponto decimal. Assim como nas principais linguagens de programação, usaremos ponto decimal (e não vírgula) para separar a parte decimal do número. Exemplos de números nesta linguagem são L_D={0, 1, 2, … 9, 10, 11, …, 99, 100, …, 0 . 1, 0 . 2, … } . Neste exemplo fica clara a dificuldade de especificação de uma linguagem infinita. O alfabeto sobre o qual L_D está definida é Σ = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9,.},ou seja, os 10 dígitos decimais mais o ponto. Uma forma de especificarmos isso é através das regras a seguir:

• N → L (um número N pode ser uma lista de dígitos L)
• N → L . L (N pode ser uma lista de dígitos L seguida de outra lista L)
• L → D (uma lista de dígitos L pode ser um dígito D)
• L → LD (uma lista de dígitos L pode ser outra lista L seguida de um dígito D)
• D → 0 (uma dígito D pode ser o dígito 0)
• D → 1 (uma dígito D pode ser o dígito 1)
• D → 2 (uma dígito D pode ser o dígito 2)
• D → 3 (uma dígito D pode ser o dígito 3)
• D → 4 (uma dígito D pode ser o dígito 4)
• D → 5 (uma dígito D pode ser o dígito 5)
• D → 6 (uma dígito D pode ser o dígito 6)
• D → 7 (uma dígito D pode ser o dígito 6)
• D → 8 (uma dígito D pode ser o dígito 8)
• D → 9 (uma dígito D pode ser o dígito 9)

Neste caso, podemos concluir que 1.23 é uma cadeia especificada por esta gramática, porque: N é um número (numeral); devido à regra N → L . L, L . L é um número (numeral decimal); mas devido à regra L → D, D . L é um numeral decimal. Seguimos a sequência, sem indicar as regras: Se D . L é um numeral, 1.L é um numeral, portanto 1.LD é um numeral, assim 1.DD é um numeral, portanto 1 . 2 D é um numeral, logo 1 . 23 também é um numeral.

Neste caso dizemos que N gera 1 . 23 . O processo pode ser representado pelo símbolo ⇒, da seguinte forma:

N ⇒ L . L ⇒ D . L ⇒ 1.L ⇒ 1.LD ⇒ 1.DD ⇒ 1 . 2 D ⇒ 1 . 23

A essa especificação damos o nome de gramática. Observando a especificação com mais detalhes, podemos observar que ela possui os seguintes elementos:

• Um alfabeto sobre o qual a linguagem é definida, chamamos os elementos deste alfabeto de símbolos terminais: T = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9,.}
• Um conjunto de símbolos auxiliares, aos quais chamamos de símbolos não terminais ou variáveis: V={N, L, D};
• Um conjunto de regras que indicam como os símbolos são substituídos para gerar uma cadeia da linguagem: P={N→L, N→L.L, L→D, L→LD, D→0, D→1, D→2, D→3, D→4, D→5, D→6, D→7, D→8, D→9} . Cada regra da forma L→ω indica que podemos substituir qualquer ocorrência de L por ω na palavra (cadeia) que está sendo gerada.
• Uma das variáveis de V designada por símbolo inicial, símbolo do qual se iniciam as derivações, neste caso: N .

Neste curso apresentamos o conceito de par ordenado, por meio do qual teremos a igualdade (x₁, x₂) = (y₁, y₂) se, e somente se, x₁ = y₁ e x₂ = y₂.

De uma forma mais geral do que triplas ou quádruplas ordenadas, chamamos de tupla a (x₁, x₂, …, x_n) e dizemos que (x₁, x₂, …, x_n) = (y₁, y₂, …, y_n) se, e somente se, para todo o i ∈ { 1, 2, …,}, x_i = y_i . Com este conceito de tuplas, podemos passar a uma definição mais formal de gramática. (MENEZES, 2000)

Uma gramática G é uma tupla (V, T, P, S) onde:

• V é um conjunto finito não vazio de variáveis.
• T é um conjunto finito não vazio de símbolos terminais.
• P é um conjunto finito de regras de produção da forma: α→β onde α, β ∈ (V∪T)^*, onde α tem ao menos uma variável.
• S ∈ V é o símbolo inicial.

Anteriormente estudamos o conceito de relação. O funcionamento da gramática se dá através da relação ⇒ _G ou simplesmente ⇒. O domínio e o contradomínio desta relação é o conjunto (V∪T)^*. Se G = (V, T, P, S), dizemos que α ⇒ _G β quando α = δ₁α₁δ₂ e β = δ₁β₁δ₂ e a regra α₁→β₁ está em P . Ou seja, se uma regra da gramática descreve como podemos trocar α₁, um pedaço de α igual ao lado esquerdo de uma regra, pelo lado direito da mesma regra, obtendo β. Neste caso dizemos que α deriva β. Observe que α₁ pode ocorrer em mais de uma posição em α e que a aplicação da regra α₁→β₁ pode ser aplicada em qualquer destas posições. Devemos aplicar as regras até que não haja mais não variáveis.

Vamos considerar o seguinte exemplo: uma gramática análoga à gramática vista para números decimais. Entretanto, esta gramática só possui os dígitos 0 e 1, gerando os números de ponto flutuante na base binária. G=(V, T, P, N), onde:

• T = { 0, 1 };
• V = { N, L, D } ;
• P= { N → L, N → L . L, L → D, L → LD, D → 0, D → 1} .

Para esta gramática temos os seguintes exemplos de ⇒_G

• L.L⇒_GL.LD
• L.L⇒_GLD.L

Quando a gramática G está subentendida no contexto, nós a suprimimos da notação, escrevendo simplesmente:

• L.LD⇒L.L0

É muito útil escrever mais de um passo da relação ⇒_G com um único símbolo ⇒^*_G, por exemplo, se N⇒_GL.L⇒_GD.L⇒_G1.L, podemos escrever N⇒^*_G1.L. O * indica que ⇒^*_G também é reflexiva, ou seja, α⇒^*α.

Dada uma gramática G é uma tupla (V, T, P, S), dizemos que a relação ⇒^*_G ⊆ (V ∪ T)^*×(V ∪ T)^* é a menor relação tal que:

Se α ⇒_G β então α ⇒^*_G β .

• Para todo  ω ∈ (V∪T)*, ω ⇒^*_G ω .

• Para todos α, β, γ ∈ (V∪T)^*, se α⇒^*_G β e β⇒^*_Gγ então α ⇒^*_Gγ .

Esta notação é lida como “deriva em zero ou mais passos”. Por  exemplo, N ⇒^*_G 1 . L é pronunciado “N deriva em zero ou mais passos 1.L “.

A relação ⇒^*_G pode ser definida de forma sucinta como ⇒^*_G é o fecho reflexivo-transitivo de ⇒_G

Considere a gramática G = (V, T, P, S) onde:

• V = { S, B }
• T = { a }
• P = { S → aB, B → ε }

Esta gramática gera uma única sentença, a saber, a sentença “a”. A sentença pode ser obtida pela derivação: S ⇒ aB ⇒ a . Observe que no segundo passo foi aplicada a regra B → ε . Esta regra indica que B pode ser substituído pela cadeia vazia. Essa gramática é bastante simples e gostaríamos de descrevê-la de forma mais simples do que a apresentada acima. Podemos fazer isso adotando algumas convenções. Convencionamos que as variáveis serão sempre letras maiúsculas e que os demais símbolos serão terminais. Além disso, o símbolo inicial é o lado esquerdo da primeira regra apresentada. De posse desta convenção, podemos apresentar a mesma gramática de uma forma muito mais concisa. Poderíamos definir a gramática anterior em duas linhas, simplesmente como:

• S → aB,
• B → ε

Podemos agora definir a linguagem gerada pela gramática G = (V, T, P, S) como o conjunto de todas as sentenças α∈T^* tais que S ⇒^*_G α . Escrevemos esta linguagem como L (G) .

Dada uma gramática G é uma tupla (V, T, P, S), dizemos que a linguagem gerada por G é:

L (G) = {ω∈T^*|S ⇒^*_Gω}.

Uma vez que definimos o que é gramática e o que é a linguagem gerada por esta gramática, podemos nos perguntar: dada uma gramática G e a uma sentença ω, como determinar se ω∈L(G)? Este problema é o problema da análise sintática. Podemos dizer que todo o conteúdo do curso daqui em diante está relacionado com este problema. Vamos resolvê-lo por partes, para diferentes “tipos” de gramática, de acordo com a sua complexidade.

Você deve ter percebido que as regras de uma gramática podem ter diferentes formatos. Por exemplo, considere o formato onde do lado esquerdo só há uma variável, ou seja, da forma N → γ . Tais
regras indicam que qualquer ocorrência de N na palavra que está sendo gerada pode ser substituída por γ . Ou seja, o N pode ser substituído por γ em qualquer posição que ele ocorra. Regras com este formato são chamadas de regras livres de contexto, isto é, a regra indica que se pode substituir N por γ independentemente do contexto em que N aparece.

A regra A → aA pode ser aplicada na forma sentencial (cadeia de símbolos terminais e não terminais) ABACAB em cada uma das 3 posições do símbolo não terminal A. Para percebermos a diferença das  regras livres de contexto, vamos contrastar com a regra AB→aAB .  Esta regra, em função do B no lado esquerdo, só pode ser aplicada à primeira e à terceira ocorrência de A em ABACAB, pois a segunda ocorrência não tem um B justaposto à direita. De fato, a aplicação se dá sobre o AB e só há duas ocorrências de AB na palavra ABACAB . Portanto, ao aplicarmos esta regra, que não é livre de contexto, à primeira ocorrência de AB na palavra ABACAB temos aABACAB e caso apliquemos à segunda ocorrência de AB teremos ABACaAB. Note que podemos continuar a aplicar esta regra às palavras resultantes indefinidamente. A este tipo de regra, que possui mais de um símbolo à esquerda da seta, denominamos regras sensíveis ao contexto, ou dependentes de contexto, sempre que o lado direito tiver mais ou tantos símbolos que o lado esquerdo. Caso contrário, ou seja, se o lado direito possuir menos símbolos que o esquerdo, temos o tipo mais geral de regra. Ou seja, uma regra da forma α→β é sensível ao contexto se, e somente se, |α|≤|β|. Por hora, basta entendermos que isto contempla regras da forma α₁Aα₂→α₁γα₂, com γ não sendo a palavra vazia. Veja, esta última regra basicamente diz que A é γ no contexto de α₁ à esquerda e α₂ à direita.

Existem casos particulares de regras livres de contexto que são importantes por serem mais simples e ainda permitem a geração de linguagens infinitas. Regras nas formas A→aB, A→ ε ou A→b são chamadas de regulares. Entende-se que A e B representam duas variáveis quaisquer (podendo ser a mesma), enquanto a e b representam dois terminais quaisquer.

Considere a gramática:

• A → aA
• A → b

Podemos ver que A ⇒ aA, portanto A ⇒^*aaA, A ⇒^* aaaA etc. Usando a notação a^k para indicar uma sequência de k a ́s, teremos que A ⇒^*a^kA, com k > 0 e, portanto, a linguagem gerada por A é formada pelas palavras a^kb, com 0 < k, pois uma vez aplicada a regra A→b não teremos mais variáveis na palavra. Existe, entretanto, um fato bastante relevante nas derivações de a^kb : A cadeia sendo gerada só possui uma ocorrência de variável, e esta está sempre no final da cadeia. Dada uma gramática G = (V, T, P, S), segue um resumo dos possíveis tipos de regras com as respectivas denominações:

• Regra regular: A→b, A→ε ou A→aB, com A, B ∈ V e a, b ∈ T ;
• Regra livre de contexto: A→γ, com A∈V e γ∈(V∪T)^*;
• Regra sensível ao contexto: α→β, com α, β∈(V∪T)^* e |α|≤|β|; ou S →ε, se S não aparece do lado direito de nenhuma regra;
• Regra geral: Não possui restrição além daquela na definição de gramática, que obriga a existir ao menos uma variável no lado esquerdo da regra.

Das denominações acima podemos constatar que toda regra regular é livre de contexto, toda livre de contexto cujo lado direito é não vazio é sensível ao contexto e toda sensível ao contexto é geral (GARCIA, 2017). Por outro lado, existem regras gerais que não são sensíveis ao contexto, regras sensíveis ao contexto que não são livres de contexto e finalmente regras livres de contexto que não são regulares. Temos uma hierarquia de regras. Vejamos como esta hierarquia de regras dá origem a uma hierarquia de linguagens.

Uma gramática é dita ser de certo tipo (regular, livre de contexto, sensível ao contexto, geral), se, e somente se, todas as suas regras são daquele tipo. Uma linguagem é de certo tipo Ti, se, e somente se, existe uma gramática do tipo Ti que gera a linguagem. Dizer então que uma linguagem não é de certo tipo é equivalente a dizer que não existe gramática daquele tipo capaz de gerar a linguagem.

Seja a gramática G₁:

• A → aA
• A → b

G₁ só possui regras regulares, portanto é uma gramática regular. A linguagem L = {a^kb, k>0} é gerada pela gramática regular G₁, portanto L é regular.

Seja a gramática G₂:

• A → aaA
• A → aA
• A → b

G₂ possui uma regra que não é regular, portanto a gramática G₂ não é regular. Entretanto, a linguagem L(G₂) é regular, pois L(G₂)=L(G₁), e basta que exista uma gramática regular que a gere para que a linguagem seja regular.

A hierarquia de Chomsky é justamente a afirmação que as linguagens formam uma hierarquia a partir dos tipos das gramáticas que são capazes de gerá-las. Cada tipo gramatical também nos indicará o mecanismo autômato capaz de resolver o problema da análise sintática para aquele tipo de gramática. Na sua forma menos detalhada, a hierarquia de Chomsky é mostrada de acordo com a tabela abaixo:

Tipos de Gramáticas	Regras	Exemplos de Linguagens geradas por estas gramáticas
Regulares	A→b, A→ε ou A→aBA, B∈V*, a, b∈ T *	anbm, n, m>0
Livres de Contexto	A→γ | γ∈(V∪T)*	anbn, n>0
Sensíveis ao Contexto	α→β, com α, β∈(V∪T)*e |α|≤|β|; ou S→ε, se S não aparece do lado direito de nenhuma regra;	anbncn, n>0
Irrestrita ou geral	α→β, com α, β∈(V∪T)* α tem pelo menos símbolo de V .	–

A tabela acima apresenta quatro tipos de gramáticas, o objetivo é sinalizar o que será visto nas próximas aulas, nelas serão vistos cada um destes tipos com maiores detalhes. Em particular, na próxima aula serão abordadas Linguagens Regulares, Autômatos Finitos e Expressões Regulares, assuntos mais concretos e que possuem diversas aplicações.