II - INTRODUÇÃO

II - INTRODUÇÃO

• Introdução• Definição• Conceitos Básicos de Linguagem

II - INTRODUÇÃO

II - INTRODUÇÃO

• Introdução

•Desenvolvida originalmente em 1950• Objetivo: Desenvolver teorias relacionadas

com a Linguagem natural

• Logo verificou-se a importância para o estudode linguagens artificiais e em especial paralinguagens originárias na Ciência daComputação

• Nestas condições as Linguagens formais sedesenvolveram significativamente e comdiversos enfoques:

II - INTRODUÇÃO

II - INTRODUÇÃO

• Introdução

• Exemplos: Análise léxica e sintática delinguagens de programação, modelos desistemas biológicos, desenho de hardware erelacionamento com linguagens naturais.

• Sintaxe x SemânticaUma linguagem de programação pode ser

vista de duas formas: como entidade livre(sem significado associado) ou comoentidade com significado associado.

II - INTRODUÇÃO

II - INTRODUÇÃO

• Introdução

• Sintaxe: Trata das propriedades livres dalinguagem (verificação gramatical deprogramas). Manipula símbolos semconsideração dos seus correspondentessignificados.

• Semântica: Tem o objetivo de dar umainterpretação para a linguagem (significadoou valor para um determinado programa)

II - INTRODUÇÃO

II - INTRODUÇÃO

• Introdução

Abordagem

Nesta disciplina dedica-se em realizar otratamento sintático de linguagens linearesabstratas com fácil associação às linguagenstípicas da Ciência da computação.

Abordagem Definição Formalismo Obs:

Operacional Autômato Reconhecedor Máquina abstrata baseada em estados.

Axiomático Gramática Gerador Associa regras à componentesda linguagem

Denotacional Expressões Regulares

Gerador Define-se uma função que caracteriza o conjunto de palavras adimissiveis na linguagem

II - INTRODUÇÃO

II - INTRODUÇÃO

• Definição

Unidade de Controle

a a a a b b b bFita de entradaPalavra ou string

q1 q2 q3 q4

Função Transição

Linguagem

alfabeto

L

D

aa

Linguagens Formais: É o conjunto de palavrassobre um alfabeto.

Autômato: É uma máquina de estado compostade três partes.

II - INTRODUÇÃO

II - INTRODUÇÃO

• Conceitos Básicos de Linguagem

Segundo o dicionário Aurélio, linguagem é“o uso da palavra escrita ou articuladacomo meio de expressão e comunicaçãoentre pessoas”.

Definição não suficientemente precisapara permitir o desenvolvimentomatemático de uma teoria sobrelinguagens.

II - INTRODUÇÃO

II - INTRODUÇÃO

• Conceitos Básicos de Linguagem

Símbolo (ou caractere): É uma entidade abstratanão definida formalmente. Ex: letras, números,caracteres especiais.

Alfabeto : Conjunto finito de símbolos. Ex:={a,b,c}.

Palavra (String), Cadeia de Caracteres ouSentença: É uma sequência finita de símbolos(do alfabeto) justapostos. Ex: aa, ab, 001101,/*+++-.

II - INTRODUÇÃO

II - INTRODUÇÃO

• Conceitos Básicos de Linguagem

Convenção baseado entre os símbolos e palavras:

Símbolos: a, b,...r,s,t, + (caracteres especiais)

Palavras: u, v, w, x, y, z. Portanto w=aaabc (é umapalavra).

ou l: representa a palavra vazia (sem símbolo ede comprimento nulo)

S*: é o conjunto de todas as palavras possíveissobre um alfabeto S.

S+=S* - {} :

II - INTRODUÇÃO

II - INTRODUÇÃO

• Conceitos Básicos de Linguagem

Comprimento: O comprimento de uma palavra w,representado por |w| consiste na quantidade decaracteres que possui a palavra. Ex: w= aabca,|w|=5.

Subpalavra: Qualquer sequência contígua desímbolos de uma palavra.

Prefixo: Qualquer sequência contígua de símbolosde uma palavra a partir do símbolo inicial.

Sufixo: Qualquer sequência contígua de símbolosde uma palavra finalizando com o símbolo final

II - INTRODUÇÃO

II - INTRODUÇÃO

• Conceitos Básicos de Linguagem

Exemplo:Dada a palavra: abcb, do alfabeto {a,b,c}.

Determine os prefixos sufixo e subpalavras.

Prefixos: ,a,ab,abc,abcb

Sufixos: ,b,cb,bcb,abcb

Subpalavras: , a, ab, abc, abcb, b, cb, bcb, bc, c.|abcb|=4 e ||=0

Linguagem Formal: É o conjunto de palavras sobreo alfabeto.

II - INTRODUÇÃO

II - INTRODUÇÃO

• Conceitos Básicos de Linguagem

Dado o alfabeto: S={a,b}

a) O conjunto vazio e o conjunto formado com apalavra vazia são linguagens sobre S.

L1={}L2={}

b) O conjunto de palíndromos (palavras que têm amesma leitura da esquerda para direita e vice-versa) sobre o alfabeto S, é um exemplo delinguagem infinita. Assim: , a, b, aa, bb, aba, ...são palavras desta linguagem.

L1L2

II - INTRODUÇÃO

II - INTRODUÇÃO

• Conceitos Básicos de Linguagem

Operações em Linguagens

Concatenação: É a operação binária, definidasobre a linguagem, a qual associa cada par depalavras a uma palavra formada pelajustaposição da primeira com a segunda.

Exemplo: v=ab, w=bcvw=abbc, wv=bcab

Propriedades:a) associativa: v(wx)=(vw)xb) Elemento neutro: w=w É o elemento neutro

da concatenação

II - INTRODUÇÃO

II - INTRODUÇÃO

• Conceitos Básicos de Linguagem

Observação: uma concatenação definida sobreuma linguagem L não é, necessariamente,fechada sobre L.

Exemplo: dado: S={a,b,c}

Seja L uma linguagem cujas palavras possuem doiscaracteres: L={aa, ab, bc, bb, ac, cc, ....}

A concatenação de quaisquer duas palavras destalinguagem formará palavras de quatrocaracteres, o que não faz parte da linguagem.

Concatenando aa com bc teremos: aabc

II - INTRODUÇÃO

II - INTRODUÇÃO

• Conceitos Básicos de Linguagem

Concatenação sucessiva: É a concatenação deuma palavra com ele mesma.

Exemplos:a) ww0=wn=wn-1w, para n>0

b) w=wn=, para n>0wn é indefinida para n=0

II - INTRODUÇÃO

II - INTRODUÇÃO

• Conceitos Básicos de Linguagem

Exemplo: dadas as palavras: u=abc e v=cbauu=u2=abcabc=(abc)2

uvvu=uv2u=abccbacbaabc=abc(cba)2abc=abc2bacba2bc

II - INTRODUÇÃO

II - INTRODUÇÃO

Por enquanto!!!!

II - INTRODUÇÃO

II - INTRODUÇÃO

• Conceitos Básicos de Linguagem

Gramática: É uma quádrupla

G=(V, T, P, S)V: conjunto finito de variáveis (não-terminais);

P: conjunto finito das regras de produção.Regras de produção são pares decomponentes tal que a primeira componenteé palavra de (VUT)+ e a segunda componenteé palavra de (VUT)*;

𝑉 ∩ 𝑇 = ∅;T: conjunto finito de não variáveis (terminais)

S: Elemento de V denominado variável inicial.

II - INTRODUÇÃO

II - INTRODUÇÃO

• Conceitos Básicos de Linguagem

G=(V, T, P, S)

Regra de produção: Define a condição degeração das palavras da linguagem.

Sejam (a, b) palavras, uma regra de produção érepresentada:

𝛼 → 𝛽Uma sequência de produção a partir da mesma

palavra pode ser representada:

𝛼 → 𝛽1, 𝛼 → 𝛽2, 𝛼 → 𝛽3 ≡𝛼 → 𝛽1|𝛽2|𝛽3

II - INTRODUÇÃO

II - INTRODUÇÃO

• Conceitos Básicos de Linguagem

G=(V, T, P, S)

A aplicação das regras de produção édenominada derivação.

A aplicação sucessiva das regras de produçãopermite derivar as palavras da linguagemrepresentada pela gramática.

Derivação: seja G=(V, T, P, S) uma gramática,uma derivação um par da relação denotadapor:(VUT)+[domínio] ⟹(VUT)*[contradomínio ] .

II - INTRODUÇÃO

II - INTRODUÇÃO

• Conceitos Básicos de Linguagem

G=(V, T, P, S)

𝛽 → 𝛽𝑢𝛽𝑡𝛽𝑤

A relação ⟹ é indutivamente definida comosegue:

• Para toda produção da forma S→ 𝛽 (aprimeira componente é o símbolo inicial deG) tem-se que:

• Para todo o par 𝛼 ⟹ 𝛽, onde b=bubvbw, sebv →bt é regra de P então:

𝑆 ⟹ 𝛽

Portanto, derivação é a substituição de umasubpalavra de acordo om as regras de produção.

II - INTRODUÇÃO

II - INTRODUÇÃO

• Conceitos Básicos de Linguagem

G=(V, T, P, S)

𝑝 ∈ P

Para explicitar uma regra de produção utiliza-sea seguinte notação:

𝛼 ⟹𝑝 𝛽

Os passos sucessivos de derivação sãodefinidos da seguinte forma:

⟹∗ - Fecho transitivo reflexivo (zero ou mais passos de derivações

sucessivos).

⟹+ - Fecho transitivo da relação (um ou mais passos de derivações

sucessivos).

⟹𝑖 - exatos i passos de derivações sucessivos (i ∈ ℕ).

II - INTRODUÇÃO

II - INTRODUÇÃO

• Conceitos Básicos de Linguagem

G=(V, T, P, S)

Linguagem Gerada - L(G): A linguagem geradapela gramática G, denotada L(G) é compostapor todas as palavras de símbolos terminaisderiváveis a partir do símbolo inicial S:

𝐿 𝐺 = 𝑤 ∈ 𝑇∗/𝑆 ⇒+ 𝑤

Exemplo:

V={S,D}

T={0,1,2,...,7,8,9}

P={S→D, S → DS,D →1|2|3|4|5|6|7|8|9}

G=(V, T, P, S)

II - INTRODUÇÃO

II - INTRODUÇÃO

• Conceitos Básicos de Linguagem

G=(V, T, P, S)Exemplo:

V={S,D} T={0,1,2,...,7,8,9}

P={S→D, S → DS,D →1|2|3|4|5|6|7|8|9}

Para se obter o número 532 faz-se a sequênciade derivação:

𝑆 ⇒ 𝐷𝑆 ⇒ 𝐷𝐷𝑆 ⇒ 𝐷𝐷𝐷 ⇒ 5𝐷𝐷 ⇒ 53𝐷 ⇒ 532

Utilizando as propriedades temos:

𝑆 ⇒∗ 532

𝑆 ⇒+ 532

𝑆 ⇒6 532

- Fecho transitivo reflexivo

- Fecho transitivo da relação

- Exatos 6 passos de derivações sucessivos.

II - INTRODUÇÃO

II - INTRODUÇÃO

• Conceitos Básicos de Linguagem

Gramáticas Equivalentes: Duas gramáticas G1 eG2 são ditas equivalentes se, e somente se,GERA(G1)=GERA(G2).

Convenções:

• A,B,C....S,T, - símbolos para variáveis;

• a,b,c,d...,s,t – símbolos para terminais;

• u,v,w,x,y,z – palavra de símbolos terminais.

• a,b,... – palavras para símbolos variáveis eterminais

II - INTRODUÇÃO

II - INTRODUÇÃO