Conceitos Básicos

Prévia do material em texto

Profª. PhD. Larissa Luz Gomes 
lariluz@yahoo.com.br 
 Aula 1 – Conceitos Básicos 
Aspectos Teóricos da 
Computação - ATC 
Visão Geral de Linguagens 
Formais 
Visão Geral de Linguagens 
Formais 
 Teoria das Linguagens Formais 
 Desenvolvida na década de 1950 
 Objetivo inicial: desenvolver teorias relacionadas 
com as linguagens naturais 
 Hoje 
 Importante para o estudo de linguagens artificiais (em 
especial, para as linguagens originárias na Ciência da 
Computação) 
 
 
Sintaxe e Semântica 
Linguagens Formais 
Preocupa-se com os problemas sintáticos das linguagens 
Historicamente 
O problema sintático foi reconhecido antes do problema 
semântico. 
Foi o primeiro a receber um tratamento adequado. 
São de tratamento mais simples que os semânticos. 
 
Visão Geral de Linguagens 
Formais 
Conseqüência 
Grande ênfase à sintaxe. 
Ao ponto de levar à ideia de que, questões das 
linguagens de programação resumiam-se às questões 
da sintaxe. 
A sintaxe basicamente manipula símbolos e não 
considera os correspondentes significados. 
Mas, para resolver qualquer problema real é necessário 
dar uma interpretação semântica aos símbolos. 
Exemplo: "estes símbolos representam os inteiros” 
Visão Geral de Linguagens Formais 
Atualmente 
Teoria da sintaxe possui construções matemáticas 
bem definidas e universalmente reconhecidas como 
exemplo: 
 Gramáticas de Chomsky. 
Visão Geral de Linguagens 
Formais 
Sintaxe 
Trata das propriedades livres da linguagem “forma” 
Exemplo: verificação gramatical de programas 
Semântica 
Fornece uma interpretação para a linguagem 
Exemplo: 
Um significado ou valor para um determinado programa 
Visão Geral de Linguagens 
Formais 
Visão Geral de Linguagens 
Formais 
Sintaticamente “errado” 
Não existe uma noção de programa “errado”. 
Neste caso, simplesmente não é um programa. 
 
Sintaticamente “correto” 
Pode não ser o programa que o programador esperava escrever. 
 
Programa “correto” ou “errado” 
Deve considerar se modela adequadamente o comportamento 
desejado. 
Conceitos Básicos 
Conceitos Básicos 
Alfabeto ou Vocabulário 
É o conjunto finito de símbolos e não vazio. 
Exemplo: 
{A, B, C, ...Z} (Alfabeto de todas as letras maiúsculas) 
{a, b, c, ...z} (Alfabeto de todas as letras maiúsculas) 
{0, 1} (Alfabeto binário) 
 
OBS: Convencionou-se adotar o símbolo Σ para denotar um 
alfabeto, entretanto isto não é uma regra geral. 
Conceitos Básicos 
Sentença ou palavra ou cadeia ou string definida 
sobre um alfabeto. 
é uma seqüência de símbolos escolhidos de um alfabeto. 
Exemplo: 
Alfabeto V = {0,1} 
Sentenças válidas = {0,1,00,01,10,11, ..., 001} 
A sentença vazia é a sentença que não contém 
símbolos, possuindo tamanho 0. É representada por 
Ω ou ε. 
V* = conjunto de todas as sentenças compostas de símbolos de 
V incluindo a sentença vazia. 
V+ = V* - (ε) 
Conceitos Básicos 
Tamanho ou comprimento de uma sentença 
é dado pelo número de símbolos que compõem a 
sentença. 
Exemplo: 
Alfabeto V = {a,b,c} 
Sentenças w = ab 
Tamanho |w| = 2 
Conceitos Básicos 
Potência de um alfabeto 
Se Σ é um alfabeto, definimos Σk, como o conjunto de 
todas as strings de comprimento k, onde o símbolo de 
cada uma das strings está em Σ. 
Exemplos: 
Se Σ = {0,1}, 
então Σ1 = {0,1}; 
 Σ2 = {00, 01, 10, 11}; 
 Σ3 = {000, 001, 010, 011, 100, 101, 110, 111} 
Conceitos Básicos 
Todas as strings de um alfabeto 
É o conjunto de todas as palavras compostas por 
símbolos de Σ, incluindo a sentença vazia. 
Σ* = Σ1 U Σ2 U Σ3 ... 
Notação: Usa-se a notação Σ+ para indicar o 
conjunto Σ* - {ε}. 
Conceitos Básicos 
Exemplos: Σ = {0,1} 
 Σ* = {Ω, 0, 1, 00, 01, 10, 11, 000, 001, ...} 
 
Notação: Usa-se a notação + para indicar o 
conjunto Σ* - {Ω}. 
 Σ+ = {0, 1, 00, 01, 10, 11, 000, 001, ...} 
 
Linguagens e Métodos de 
Representação de Linguagens 
 
Conceitos Básicos 
Linguagens e Métodos de Representação de 
Linguagens 
Definição Informal de Linguagem: 
 Linguagem é o uso da palavra articulada ou escrita como 
forma de comunicação entre pessoas. 
Definição de Linguagem Formal: 
é qualquer conjunto de sentenças sobre um alfabeto, ou seja, 
uma linguagem L sobre um alfabeto V é um subconjunto de 
V* . 
Exemplos: L(Σ) = {01, 0011, 000111, ...} 
Conceitos Básicos 
As linguagens possuem sempre um método (ou regra) 
de formação. 
Conforme o número de sentenças que possuem, as 
linguagens se classificam em: 
Finitas 
Vazias 
 Infinitas 
Conceitos Básicos 
Pode usar um formador de conjuntos, como {w/ algo 
sobre w}. 
Essa expressão é lida como o conjunto de palavras w tais 
que (seja o que for dito sobre w à direita da barra 
vertical). Alguns exemplos são: 
L = {w/ w consiste em número igual de 0’s e 1’s} 
L = {w/ w é um número inteiro binário primo} 
L = {w/ w é um programa sintaticamente correto} 
 
Conceitos Básicos 
Pode-se substituir w por alguma expressão com 
parâmetros e descrever as palavras na linguagem 
declarando condições sobre os parâmetros. 
 
O primeiro com o parâmetro n, o segundo com os 
parâmetros i e j. Esta forma de representar uma 
linguagem é conhecida como Método Algébrico ou 
Português Matemático, por alguns autores. 
 
Exemplo 1: L = {0 1n, n > = 1} 
Exemplo 2: L = {0i1j, 0 <= i <= j} 
Métodos de Representação 
de Linguagem 
Métodos de Representação de 
Linguagem 
 Existem vários métodos para representação de linguagens, como 
por exemplo: 
1. Enumeração das cadeias de símbolos que formam as suas 
sentenças (listando as palavras). Só para uma linguagem finita. 
2. Através de um conjunto de leis de formação das cadeias 
(definindo um mecanismo que gera sistematicamente as 
sentenças da linguagem em alguma ordem – GERAÇÃO). Ao 
conjunto de leis de formação dá-se o nome de Gramática. 
• Exemplo: gramática 
3. Através de regras de aceitação de cadeias. (definindo um 
algoritmo que determine se uma sentença pertence ou não à 
linguagem – RECONHECIMENTO). Às regras de aceitação 
dá-se o nome de Reconhecedor ou Autômatos). 
• Exemplo: autômato finito 
Conceitos Básicos 
O método mais comum de se especificar um 
procedimento para um computador é através de 
uma linguagem de programação. 
Conceitos Básicos 
Uma linguagem de programação é definida como um 
como um conjunto de símbolos chamado alfabeto e por 
um conjunto de regras que vai especificar como 
compor esses símbolos(sintaxe) e quais as ações 
associadas a eles. 
 
Uma seqüência de símbolos de uma linguagem é 
chamada programa. 
Conceitos Básicos 
Dois mecanismos ou modelos matemáticos 
muito importantes que estão por trás de uma 
linguagem são: 
 
Gramáticas 
 
Autômatos 
Conceitos Básicos 
Autômatos 
Reconhece uma linguagem pelo processo de 
“prova” de cada elemento possível, para verificar se 
ele pertence ou não a uma linguagem. 
 
Gramática 
Outro processo importante em uma linguagem é a 
geração dela. Gerar a linguagem é o processo feito 
por um procedimento que dá como saída os 
elementos da linguagem. É o mecanismo gerador de 
sentenças. 
Gramática 
Gramática 
Notação Formal de Gramática 
Uma gramática G é definida por uma quádrupla 
 G = (N, T, P, S), onde: 
 
N – conjunto finito de símbolos variáveis ou não-terminais 
T – conjunto finito de terminais disjuntos de N 
P – conjunto finito de regras de produção 
S – é um elementodistinguido de N denominado símbolo 
inicial da gramática ou variável inicial da gramática 
 
OBS: N e T também podem ser representados por ΣN e 
ΣT ou ainda por V e T. 
Gramática 
Observações: 
 N ∩ T = Ø e convencionamos adotar 
∑= N U T 
S ε N 
P = {α → β | α ε V+ e β ε V*} 
O conjunto P das regras de produções consiste de 
expressões da forma α → β, onde α é uma palavra 
de Σ+ e β é uma palavra de Σ*(P define uma relação 
Σ*). 
Finalmente, S é um símbolo de N. 
Derivação 
Gramática - Derivação 
As regras de produção (P) definem as 
condições de geração das palavras da 
linguagem. 
A aplicação das regras de produção é 
denominada derivação de uma palavra. 
A aplicação sucessiva de regras de produção 
permite derivar as palavras da linguagem 
representadas pela gramática. 
A derivação é uma operação de substituição efetuada de 
acordo com as regras de produção da gramática. 
Representa-se esta operação pelo símbolo => 
 Logo: x α y => x β y 
Se α → β Є P e x e y Є V* 
 Para garantir que pelo menos uma derivação seja 
efetuada, a notação utilizada é +=>. Isto é: 
α1 +=> αm se 
α1 => α2, α2 *=> αm, 
α1, α2, ..., αm Є V* 
 
Gramática - Derivação 
Uma seqüência de derivações, de zero ou mais passos, 
é representada por * => 
Isto é: α1 *=> αm se 
α1 => α2, α2 => α3, ..., αm-1 => αm 
α1, α2, ..., αm Є V* 
 
Gramática - Derivação 
Exemplo de Derivação 
Exemplo 1: Dada a Gramática G1: 
G1 = ({S0, S1}, {0,1}, P, {S0}) 
P1: S0 → 0 S0 
P2: S0 → 1 S1 
P3: S1 → 0 S0 
P4: S1 → 1 
 
Encontre algumas cadeias geradas por G1 
 
Exemplo 1: Dada a Gramática G1: 
G1 = ({S0, S1}, {0,1}, P, {S0}) 
P1: S0 → 0 S0 
P2: S0 → 1 S1 
P3: S1 → 0 S0 
P4: S1 → 1 
Algumas sentenças geradas por G1: 
 P1 P1 P2 P4 
1. S0 → 0 S0 → 00 S0 → 001 S1 → 0011 
 P2 P4 
2. S0 → 1 S1 → 11 
 P2 P3 P1 P2 P4 
3. S0 → 1 S1 → 10 S0 → 100 S0 → 1001 S1 → 10011 
Exemplo de Derivação 
Exemplo 2: Dada a Gramática G2: 
G2 = ({S, M}, {a, b, c}, P, {S}), onde P: 
S → bS / aM / c 
M → bS 
 
Encontre algumas cadeias geradas por G2 
Exemplo de Derivação 
Exemplo 2: Dada a Gramática G2: 
G2 = ({S, M}, {a, b, c}, P, {S}), onde P: 
S → bS / aM / c 
M → bS 
Algumas sentenças geradas por G2: 
 P1 P2 P4 P3 
1. S → bS → baM → babS → babc 
 P2 P4 P1 P3 
2. S → aM → abS → abbS → abbc 
 P3 
3. S → c 
 P2 P4 P3 
4. S → aM → abS → abc 
 
Exemplo de Derivação 
 Exemplo 3: Dada a Gramática G3 = (ΣN, ΣT, P, S), onde: 
ΣN = {<sentença>, <SN>, <SV>} 
ΣT = {elefante, amendoim, comeu, o} 
P = {<sentença>→<SN> <SV>} 
 <SN> → <artigo> <nome-comum> 
 <SV> → <verbo> < SN> 
 <artigo> → o 
 <nome-comum> → elefante/ amendoim 
 <verbo> → comeu 
S = {<sentença>} 
Encontre algumas cadeias geradas por G3 
Exemplo de Derivação 
Exemplo 4: Dada a Gramática G4: 
G2 = ({expressão}, {+, *, (,), id}, P, {<expressão>}) 
Sendo P o conjunto das seguintes produções: 
P1: <expressão> → <expressão> + <expressão> 
P2: <expressão> → <expressão> * <expressão> 
P3: <expressão> → (<expressão>) 
P4: id 
 
Quais são alguma das cadeia gerada pela gramática G4? 
Exemplo de Derivação 
Exemplo de Derivação 
Exemplo 4: Dada a Gramática G4: 
G4 = ({expressão}, {+, *, (,), id}, P, {<expressão>}) 
Sendo P o conjunto das seguintes produções: 
P1: <expressão> → <expressão> + <expressão> 
P2: <expressão> → <expressão> * <expressão> 
P3: <expressão> → (<expressão>) 
P4: id 
Resposta: 
<expressão> P2 → <expressão> * <expressão> 
 P3 → <expressão> * (<expressão>) 
 P1 → <expressão> * (<expressão> + <expressão>) 
 P4 → id * (<expressão> + <expressão>) 
 P4 → id * (id + <expressão>) 
 P4 → id * (id + id) 
Sentença e Forma Sentencial 
Sentença e Forma Sentencial 
Uma SENTENÇA de uma linguagem é uma 
seqüência formada de terminais, obtida a partir do 
símbolo inicial da gramática desta linguagem, 
através de derivações sucessivas. 
S +=> w {w = seqüência de terminais} 
 
Uma FORMA SENTENCIAL é uma seqüência 
qualquer, composta de símbolos terminais e de 
não-terminais, obtida a partir do símbolo inicial da 
gramática através de derivações sucessivas. 
S *=> α {α = seqüência de variáveis e terminais} 
Linguagem Gerada ou Linguagem 
Definida pela Gramática L(G) 
Linguagem Gerada ou Linguagem 
Definida pela Gramática L(G 
A linguagem gerada por uma gramática G = (N, 
T, P, S) é o conjunto de todas as palavras de 
símbolos terminais deriváveis, que podem ser 
geradas a partir do símbolo inicial (S) desta 
gramática, através de derivações sucessivas. 
 
 L(G) = {w | w Є T* | S =>+ w} 
Linguagem Gerada – L(G) 
Exemplo 1: Qual é a linguagem gerada por esta 
gramática? 
 
 G = ({S}, {0,1}, P, S) 
 P = {S → 0S1 
 S → 01} 
 
Linguagem Gerada – L(G) 
Exemplo 1: Linguagem que gera números de 0’s e 
1’s iguais 
 G = (N, T, P, S) 
G = ({S}, {0,1}, P, S) 
P = {S → 0S1 
 S → 01} 
 
S => 0S1 => 00S11 => 03S13 => ...0n-1 S1n-1 
 => 0n1n 
L(G) = {0n1n | n >= 1} 
 
Linguagem Gerada – L(G) 
Exemplo 2: Qual é a linguagem gerada pela 
gramática abaixo: 
 
G = ({N,D}, {0,1,2,...,9}, P, S) 
P = {N → D, 
 N → DN, 
 D → 0| 1| ...|9 
 S => N | D} 
Mostre a derivação do número 17987? 
 
 
Linguagem Gerada – L(G) 
Exemplo 2: Qual é a linguagem gerada pela 
gramática abaixo: 
 
G = ({N,D}, {0,1,2,...,9}, P, S) 
P = {N → D, 
 N → DN, 
 D → 0| 1| ...|9 
 S => N | D} 
Linguagem que gera os números naturais 
 
 
Linguagem Gerada – L(G) 
Exemplo 3: 
 G = (N, T, P, S) 
G = ({S,X,Y,A,B,F},{a,b}, P, S) 
P = {S  XY, 
 X XaA | XbB | F 
 Aa aA, Ab bA, AY Ya, 
 Ba Ab, Bb  Bb, BY  Yb 
 Fa  aF, Fb  bF, FY ε} 
Qual é a linguagem gerada por esta gramática, mostre 
essa derivação. 
 
Hierarquia de Chomsky 
Hierarquia de Chomsky 
O estudo das linguagens formais teve um forte 
impulso no final da década de 50, quando o 
lingüista Noam Chomsky publicou dois artigos 
apresentando o resultado de suas pesquisas 
relativas à classificação hierárquica das 
linguagens. 
Até então a teoria dos autômatos se apresentava 
razoavelmente evoluída, porém a das linguagens 
formais ainda não havia de fato se estabelecido 
como disciplina. 
Hierarquia de Chomsky 
A partir dos artigos houve uma significativa 
concentração de pesquisas na área das 
linguagens formais. 
Esta por sua vez teve a oportunidade de se 
consolidar definitivamente, a partir do final da 
década de 60, como disciplina coesa e 
fundamental para as área de engenharia e 
ciência da computação. 
Hierarquia de Chomsky 
A classificação das linguagens por ele propostas 
ficou conhecida como Hierarquia de 
Chomsky. 
Tem como principal mérito agrupar as 
linguagens em classes, de tal forma que elas 
possam ser hierarquizadas de acordo com a sua 
complexidade. 
Hierarquia de Chomsky 
Como resultado, é possível antecipar as 
propriedades fundamentais exibidas por uma 
determinada linguagem, ou mesmo vislumbrar 
os modelos de implementação mais adequados 
para a sua realização de acordo com a classe a 
que pertençam.Hierarquia de Chomsky 
Deste modo o interesse prático na Hierarquia de 
Chomsky se deve ao fato de ela viabilizar a 
escolha de formas mais econômicas para a 
realização dos reconhecedores das linguagens, 
de acordo com a classe que pertencem. 
Evitando assim, o uso de formalismos mais 
complexos e o emprego de reconhecedores 
ineficientes para linguagens de menor 
complexidade. 
Hierarquia de Chomsky 
Do ponto de vista estritamente de engenharia, a 
Hierarquia de Chomsky permite determinar e 
selecionar o modelo de implementação (no que 
diz respeito apenas ao reconhecedor sintático) 
de menor custo para cada linguagem. 
Hierarquia de Chomsky 
Chomsky idealizou uma forma de classificar 
gramáticas segundo suas regras de produção, isto é, 
segundo o grau de liberdade apresentado por suas 
produções. 
Além de fazer esta classificação Chomsky notou que 
cada um dos níveis gramaticais propostos por ele 
poderia ser reconhecido por um autômato distinto 
Hierarquia de Chomsky 
Este fato vai permitir especificar o front-end de um 
compilador de forma mais ou menos automática a partir 
dos autômatos reconhecedores definidos por ele. 
O quadro a seguir apresenta os níveis hierárquicos 
propostos por Chomsky. 
Gramática de Chomsky 
Hierarquia de Chomsky 
Para Chomsky existem 4 (quatro) tipos de 
Gramática (gramáticas gerativas): 
Tipo 0 são chamadas GI (Gramáticas não restritivas ou 
Gramáticas Irrestritas ou Gramáticas com Estrutura de 
Frase) 
Tipo 1 são chamadas GSC (Gramáticas Sensíveis ao 
Contexto) 
Tipo 2 são chamadas GLC (Gramáticas Livres de 
Contexto) 
Tipo 3 são chamadas GR (Gramáticas Regulares). 
Hierarquia de Chomsky 
As gramáticas do tipo 0 contém as do tipo 1, 
que por sua vez, contém as do tipo 2, que 
contém as do tipo 3. 
Essa hierarquia é também válida para as 
linguagens. 
Hierarquia de Chomsky 
Tipos de Gramática 
Tipos de Gramáticas 
Tipo 0 – Gramáticas Irrestritas (GI) 
São definidas pelas seguintes regras de produção: 
 
• P = {α→β | α Є V+, β Є V*} 
 
Ou seja, do lado esquerdo da produção pode haver uma 
seqüência de quaisquer símbolos. Do lado direito da produção 
pode haver qualquer seqüência de símbolos, inclusive a 
sentença vazia. 
A gramática Irrestrita também é conhecida como a gramática 
onde nenhum limitação é imposta. 
São capazes de reconhecer linguagens Recursivamente 
Enumeráveis 
 
Tipos de Gramáticas 
Exemplo de Gramáticas Irrestritas (GI) 
 
Tipos de Gramáticas 
Exemplo de Gramáticas Irrestritas (GI) 
 
Tipos de Gramática 
• Tipo 1 – Gramáticas Sensíveis ao Contexto (GSC) 
 Para toda produção 
 α → β Є P 
 |α| <= |β| 
 Ou seja, o comprimento da sentença do lado esquerdo deve ser 
menor ou igual ao comprimento da sentença do lado direito da 
produção. 
 Do lado direito não é aceita a sentença vazia. 
Tipos de Gramática 
• Tipo 1 – Gramáticas Sensíveis ao Contexto (GSC) 
 Se às regras de substituição for imposta a restrição de que 
nenhuma substituição possa reduzir o comprimento da forma 
sentencial à qual a substituição é aplicada, cria-se uma classe 
de gramáticas ditas sensíveis ao contexto. 
 As gramáticas que obedecem a estas restrições pertencem ao 
conjunto das Gramáticas Sensíveis ao Contexto, ou do Tipo 1. 
 Chamam-se linguagens do tipo 1 todas aquelas que podem ser 
geradas por alguma gramática do tipo 1. 
 Note-se que todas as linguagens do tipo 1 podem ser geradas 
através de gramáticas com estrutura de frase ou do tipo 0, 
embora o inverso não seja verdade. 
Tipos de Gramática 
• Exemplo de Gramáticas Sensíveis ao Contexto (GSC) 
 
Tipos de Gramática 
• Exemplo de Gramáticas Sensíveis ao Contexto (GSC) 
 
Tipos de Gramática 
• Tipo 2 – Gramáticas Livres de Contexto (GLC) 
 
 Quando as regras de produção são todas na seguinte forma: 
• P = {α → β | α Є N e β ≠ ε} 
 Ou seja, do lado esquerdo da produção deve, sempre, ocorrer um e 
apenas um não-terminal. 
 A sentença vazia também não é aceita do lado direito da produção. 
 
• Ex: X → abcX (não interessa o contexto em que X se encontra) 
Tipos de Gramática 
•Exemplo de Gramáticas Livres de Contexto (GLC) 
 
•Exemplo 1: 
 
•G = ({E, F, T}, {i}, P, {E}) 
•P: E → T / E + T / E – T 
•T → F / T * F / T / F 
•F → i / F * * i 
 
Tipos de Gramática 
Exemplo de Gramáticas Livres de Contexto (GLC) 
• G = ({S}, {a, +, *, (, )}, P, S) 
 P = S Þ S * S 
 S Þ S + S 
 S Þ (S) 
 S Þ a 
 L(G) = conjunto das expressões aritméticas envolvendo *, 
+,( ) e a. 
Um exemplo de cadeia formada por esta gramática é a * (a 
+ a). 
Verifique que essa gramática é ambígua! 
 
Tipos de Gramática 
• Tipo 3 – Gramáticas Regulares (GR) 
 Toda produção é da forma: 
• A → aB ou 
• A → a 
 Ou seja: 
• P= {A → aX | A Є N, a Є T, X Є N U {ε}} 
 
 Do lado esquerdo da produção deve, sempre, ocorrer um e 
apenas um não-terminal e do lado direito podem ocorrer ou 
somente um terminal, ou um terminal mais um não-terminal. 
 
Exercício 
• Determine L(G), sendo: 
 
G = ({ S, B, C}, { a, b }, P, S) 
P: { S  aB|bC 
 B  bS|aBB|b 
 C  aS|bCC|a } 
Dúvidas ou Perguntas 
Próxima Aula 
 
 Exercício e 
 Gramática Regular