03_-_Linguagens_e_Gramaticas

LINGUAGENS E GRAMTICAS

Prof. Ronaldo R. Goldschmidt [email protected]

Definio de Linguagem (Aurlio): o uso da palavra

articulada ou escrita como meio de expresso e comunicao

entre pessoas.

Definio insuficiente para permitir o desenvolvimento de

uma teoria formal sobre linguagens.

Linguagem um dos conceitos mais fundamentais em

Computao e Informtica.

Conceitos como alfabeto e cadeia de caracteres so

necessrios para definir formalmente uma linguagem.


Def.: Um alfabeto um conjunto finito de smbolos (unidade

atmica) de algum tipo.

Exs.: ={a, b, c, ..., z} alfabeto romano

={0, 1} alfabeto binrio

= alfabeto vazio

={0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F} alfabeto hexa

=N o conjunto dos naturais no um alfabeto

Obs.: Cada smbolo considerado como uma unidade atmica, no

importando sua representao visual. Exemplos de smbolos: a,

abc, begin, if, 5, 1024, 2.017e4.


Obs.: Por simplicidade, em geral, os smbolos utilizados so letras,

nmeros e outros caracteres especiais tais como $, espao, #

ou *, por exemplo.

Obs.: No entanto, no h uma definio formal para smbolo. O seu

significado deve ser intudo como uma entidade abstrata, um

conceito primitivo, e aceit-lo como base para a teoria que ser

desenvolvida.


Ex.: Alfabeto da Linguagem de Programao Pascal

Conjunto de smbolos (da tabela ASCII) usados na construo

de programas:

Letras

Dgitos

Caracteres especiais como , /, dentre outros

Espao ou Branco

Obs.: O alfabeto binrio {a, b} usado com frequncia. Alm

da simplicidade, possui analogia com a representao

interna de computadores reais (o domnio de valores de

um bit binrio).


Def.: Uma cadeia (de caracteres) sobre um alfabeto uma

seqncia finita de smbolos deste alfabeto justapostos.

Ex.: Sendo ={a, b}, so exemplos de cadeias: aba, aaaa,

bababb, a, b.

Em uma linguagem de programao, uma cadeia corresponde

a um programa.

So sinnimos de cadeia: palavra, sentena ou string.

Def.: A cadeia sem smbolos chamada de cadeia vazia.

Notao: (ou ) Obs: {}


Def.: O comprimento de uma cadeia sobre um alfabeto o

nmero de smbolos contidos na cadeia. Notao: ||

o comprimento de uma cadeia qualquer

Exs.: |abra| = 4 ||=0 |xpto123|=7

Obs: Uma cadeia pode ser considerada como uma funo

:{1, 2, ..., ||} (chamada isomorfismo natural). O valor (j) corresponde ao smbolo na j-sima posio de

, onde 1 j ||.

Ex.: =abra (1)= (4) = a; (2)=b; (3)=r


Def.: Se e so cadeias, ento . (ou simplesmente ) a

concatenao da cadeia com a cadeia .

Ex.: abra.cadabra = abracadabra

Obs.: Para toda cadeia , = = ( o elemento neutro)

Obs.: |.| = || + ||

Ex.: |abra.cadabra| = |abra| + |cadabra| = 4 + 7 = 11

|abracadabra| = 11

Obs.: A operao de concatenao associativa porm no

comutativa: .(.)=(.). . .


Ex.: Concatenao de palavras u=ab v=ba uv=abba

Ex.: Concatenaes sucessivas:

u=ababab

u0=

un+1 = un .u

abra3 = abraabraabra

an = aaaa...a (o smbolo a repetido n vezes)

Obs.: O segundo e o terceiro exemplos de concatenao

sucessiva compem um exemplo de definio por

induo.


Def.: Define-se cadeia elementar (ou unitria) a qualquer

cadeia formada por um nico smbolo.

Ex: = a uma cadeia elementar pois | | = 1

Obs: Os smbolos do alfabeto da Lngua Portuguesa so

construdos a partir da concatenao de um nmero

varivel de caracteres (letras do alfabeto romano).

Nesse sentido e contexto, embora representados com

diversos caracteres, tais smbolos so considerados

cadeias elementares.


Ainda no caso do alfabeto da Lngua Portuguesa:

consideremos que ele contenha todas as palavras de nosso

idioma (conjugaes de todos os verbos, as formas

flexionadas de todos os adjetivos, substantivos, etc.).

Exemplo de cadeia:

= Exemplo de cadeia no alfabeto da Lngua Portuguesa

| | = 8

Note que o alfabeto da Lngua Portuguesa, embora extenso,

finito e pode gerar infinitas cadeias.


Verifique se so verdadeiras ou falsas as afirmativas abaixo,

justificando suas respostas.

a) Se = r.s e || = n e |r| = m Ento |s| = n - m

b) Se u2=u Ento u=

c) |un| = n|u|, para n 0

d) Se = abc Ento (4) no est definido

e) Se = abc Ento 2(4) =


Def.: Prefixo de toda cadeia obtida a partir da remoo de

0 ou mais smbolos do final de .

Ex.: A cadeia abra possui 5 prefixos: abra, abr, ab , a,

Def.: Prefixo prprio de todo prefixo de diferente de .

Ex.: A cadeia abra possui 4 prefixos prprios: abr, ab , a,


Def.: Sufixo de toda cadeia obtida a partir da remoo de

0 ou mais smbolos do comeo de .

Ex.: A cadeia abra possui 5 sufixos: abra, bra, ra, a,

Def.: Sufixo prprio de todo sufixo de diferente de .

Ex.: A cadeia abra possui 4 sufixos prprios: bra, ra, a,


Def.: Subcadeia (ou Subpalavra) de toda cadeia obtida a

partir da remoo de um prefixo e/ou um sufixo de .

Exs.: So exemplos de subcadeias de abra: br, a, ab, ra,

Def.: Uma cadeia reversa uma cadeia em que os smbolos

so escritos em ordem inversa da cadeia original. Notao:

R

Obs.: Seja = a1a2...an, com ai , i 0. Ento, a reversa de

R = an...a2a1

Ex.: = abra e R = arba


Definio formal do reverso de uma cadeia dada por induo:

(i) Se uma cadeia tal que | | = 0, ento R = =

(ii) Se uma cadeia tal que | | = n + 1 > 0, ento = ua para

algum a e R = auR

Obs.: A seguir uma ilustrao de como uma prova por induo pode

depender de uma definio dada por induo.

Teorema: Para quaisquer cadeias e , ()R = RR

Ex: (dogcat)R = (cat)R (dog)R =tacgod


Para quaisquer cadeias e , ()R = R R . Demonstrao:

(i) Sup. | | = 0

Portanto, =

Logo: ()R = ()R = R = R = R R = R R

(ii) Hiptese de Induo: se | | n, ento ()R = R R

(iii) Passo Indutivo: Seja | | = n + 1. Ento, = ua, para alguma cadeia u e a

tal que | u | = n (note que | a | = 1)

Logo: ()R = ((ua))R, pois = ua

= ((u)a)R, pois a concatenao associativa

= a(u)R, pela definio de cadeia reversa de (u)a

= auRR, pela hiptese de induo

= (ua)RR, pela definio de cadeia reversa de ua

= R R , uma vez que = ua


Def.: Uma cadeia palndroma toda cadeia tal que = R.

Exs.:

arara, seres, salas, reviver, ovo, osso, radar, ama, anilina, mamam,

socos, sapas, somos, somavamos, ala, ata, radar, rapar, mirim,

reler, reviver, sacas, siris, ame a ema, assam a massa, etc...

Ateno: Conveno de tipo para smbolos, cadeias e alfabetos:

Smbolos Letras minsculas do incio do alfabeto romano (a, b, c) ou dgitos.

Cadeias Letras minsculas do final do alfabeto romano (w, x, y, z) ou letras minsculas do alfabeto grego (, , etc..)

Alfabetos Letras maisculas do alfabeto grego (, , , etc...)


Def.: O conjunto de todas as cadeias, incluindo a cadeia

vazia, sobre um alfabeto denotado por *

Obs.: O conjunto de todas as cadeias sobre um alfabeto

definido recursivamente por:

i) * e para qualquer , vale que *

ii) para qualquer , * , vale que *

Ex: Se = {a, b}, ento:

+ = {a, b, aa, ab, ba, bb, aaa, ...}

* = {, a, b, aa, ab, ba, bb, aaa, ...}


Def.: O conjunto de todas as cadeias, incluindo a cadeia

vazia, sobre um alfabeto denotado por *

Obs.: um alfabeto finito com n elementos, mas *

infinito. Pode ser enumerado da seguinte forma:

i) Para cada k 0, todas as strings de comprimento k devem

ser enumeradas antes das de comprimento k+1

ii) As nk strings devem ser enumeradas lexicograficamente.

Ex: Se = {0, 1}, ento:

* = {, 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, ...}


Def.: Uma linguagem formal L sobre um alfabeto

qualquer subconjunto de *, L *

Exs: , , *, + so linguagens formais sobre qualquer

Obs.: Como muitas linguagens so infinitas, utiliza-se a

seguinte representao implcita de conjuntos:

L = { * / possui uma propriedade P}

Exs.: { * / = R}, linguagem de palavras palndromas

{a / *}, linguagem de palavras iniciadas por a,

{ */ (1)=a}


Def.: Uma linguagem formal L sobre um alfabeto

qualquer subconjunto de *, L *

Obs.: 2* o conjunto de todas as linguagens sobre um

alfabeto .

Ex.: Linguagem Formal: Linguagem de Programao

Uma Linguagem de Programao como Pascal formalmente

definida pelo conjunto de todos os programas (palavras) da

linguagem.

Obs: Sejam L uma linguagem formal sobre e .

Pergunta-se: L linguagem formal sobre ?


Relao entre smbolo, alfabeto, cadeia e linguagem


Relao entre smbolo, alfabeto, cadeia e linguagem

Obs: Distino entre o smbolo b e a cadeia/sentena b


Atividades Prticas

Lista de Exerccios II At o exerccio 7


Exerccio 17 da Lista II: Elabore um programa em C que apresente o valor

decimal e o glifo correspondente da tabela ASCII do smbolo 32 ao smbolo 126

(caracteres imprimveis).

Exerccio de Programao

Operaes com Linguagens (Construo de Outras Linguagens)

Obs: Linguagens so conjuntos (em essncia)

Unio

L1 L2 = { s | s L1 ou s L2 }

Ex.: { ab, ac } { ab, bc } = { ab, ac, bc }

Interseo

L1 L2 = { s | s L1 e s L2 }

Ex.: { ab, ac } { ab, bc } = { ab }



Obs: Linguagens so conjuntos (em essncia)

Concatenao

L1.L2 = { st | s L1 e t L2 }

Ex.: { ab, ac }.{ ab, bc } = { abab, abbc, acab, acbc }

Observaes:

L1. = . L1 = (demonstrao)

Concatenao no comutativa (contraexemplo)



Fechamento de Kleene (Estrela de Kleene)

Seja A uma linguagem definida sobre um alfabeto . Ento A*

uma linguagem obtida a partir de A como se segue:

A* = A0 A1 ... An ...

onde: A0 = { } e An = An-1.A, n 0

Ex.1: A = { a }

A* = { } { a } { aa } { aaa } ...

= { , a, aa, aaa, ... }






A* = A0 A1 ... An ...

onde: A0 = { } e An = An-1.A , n 0

Ex2.: A = { ab, b}

A* = { } { ab, b } { abab, abb, bab, bb } ...

= { , ab, b, abab, abb, bab, bb, ... }






A* = A0 A1 ... An ...

onde: A0 = { } e An = An-1.A , n 0

Ex3.: A =

A* = { }



Fechamento Positivo

A+ = A*.A ou A* = { } A+

Ex.: A = { a }

A+ = { , a, aa, aaa, ... }.{ a } = { a, aa, aaa, ... }

Complemento

Ex.: A = { a } = { , a, aa, aaa, ... }-{ a } = {, aa, aaa, ... }

AA *

A



Quociente

L1/L2 = { x | xy L1 e y L2 }

Exs.: { abb, acb }/{ b } = { ab, ac }

{ abb, acb }/{ b, bb } = { ab, ac, a }

Sendo:

L1 = { aib | i 0 } = {b, ab, aab, aaab, ...} L2 = { b }

L3 = { aib | i 1 } = {ab, aab, aaab, ...}

L1/ L2 = {, a, aa, aaa, aaaa, ...} = { ai | i 0 }

L1/ L3 = {, a, aa, aaa, ...} = { ai | i 0 }


Sendo:

L1 = { aib | i 0 } = {b, ab, aab, aaab, ...} L2 = { b }

L3 = { aib | i 1 } = {ab, aab, aaab, ...}

L4 = { aibci | i 0 } = {b, abc, aabcc, aaabccc, ...}

L5 = { bci | i 0 } = {b, bc, bcc, bccc, ...}

L6 = { ci | i 1 } = {c, cc, ccc, ...}

L4/ L5 =

L5/ L4 =

L1/ L5 =

L4/ L1 =

L6/ L2 =


Atividades Prticas

Lista de Exerccios II Exerccio 8


Exerccio 18 da Lista II: Elabore um programa em C que receba como entrada

duas linguagens finitas L1 e L2, ambas no vazias (e sem a cadeia vazia) e

apresente como sadas as seguintes linguagens: L1 L2, L1 L2, L1.L2.

Exerccio de Programao

Observao:

Na teoria de autmatos, um problema em geral se caracteriza

pela deciso se uma determinada cadeia pertence ou no a

uma linguagem especfica.

Em termos coloquiais, um problema pode ser expresso como

pertinncia a uma linguagem.

Em termos formais, sendo L uma linguagem formal sobre ,

ento o problema L consiste em: dada uma cadeia em *,

definir se est ou no em L.


Mtodos de Representao Finita de Linguagens:

Gramticas

Reconhecedores

Enumeraes

Obs: Os dois primeiros so formas duais de representao.

Obs: A notao usada para representar uma linguagem

chamada de metalinguagem.

Exs:

L={ * / palndroma}

L={ara, arara, ...}


Toda Linguagem possui:

Sintaxe Estruturas para representao de construes

Ex: arara L={ * / palndroma}, ={a,r}

Semntica Significado associado s construes

arara


Como uma linguagem de programao o conjunto (infinito) de

todos os programas dessa linguagem, ela requer uma definio

adequada para ser implementada computacionalmente (gramtica).

Uma gramtica um sistema formal baseado em regras de

substituio que, quando aplicadas sucessivamente, podem gerar,

de forma exaustiva, o conjunto de cadeias que compem uma

determinada linguagem. Assim, o conjunto de todas as palavras

geradas por uma gramtica define a linguagem associada.

As gramticas usadas para linguagens naturais como o Portugus

so anlogas s usadas para linguagens artificiais como o Pascal e

o C.


Consideremos a orao em Portugus: O menino atravessou a rua

distraidamente. Esta orao est sintaticamente correta, pois obedece s seguintes

regras:

Frase = Sujeito + Predicado + Complemento

Sujeito = Artigo + Substantivo

Predicado = Verbo + Objeto Direto

Objeto Direto = Artigo + Substantivo

Artigo = {o, a}

Substantivo = {menino, rua}

Verbo = {atravessou}

Complemento = {distraidamente}

E as oraes: A rua atravessou o menino distraidamente e O rua atravessou a

menino distraidamente?


Repare que artigo, substantivo e verbo so exemplos de

classes gramaticais da Lngua Portuguesa. Normalmente independem

da orao para classificarmos os smbolos. No exemplo:

Artigo = {o, a}

Substantivo = {menino, rua}

Verbo = {atravessou}

Sujeito, predicado, objeto direto so exemplos de funes

sintticas que os smbolos, isolados ou em conjunto, assumem na

orao. A caracterizao da funo sinttica depende do smbolo (ou

conjunto de smbolos) e do papel que ele exerce na orao.


Um site que permite a anlise de sentenas (parser) da Lngua

Portuguesa o VISL:

http://beta.visl.sdu.dk/visl/pt/parsing/automatic/trees.php

Exemplo:


Def.: Uma Gramtica de Chomsky, Gramtica Irrestrita ou simplesmente

Gramtica uma qudrupla ordenada:

G=(V,T,P,S) , na qual:

V e T conjuntos finitos no vazios e disjuntos de smbolos variveis e terminais, respectivamente.

P:(VT)+ (VT)* uma Relao de Produes (Regras de Substituio), sendo um conjunto finito e no vazio.

S, um smbolo destacado de V (chamado raiz ou smbolo inicial)

Regras de Produo Formato

(,) ou

1| 2| ...| n


Ex: Seja uma gramtica G=(V, T, P, N) definida por

V={N,D} T={0,1,2,...,9} P={ND, NDN, D0|1|2|...|9}

Derivao: Substituio de uma subpalavra de acordo com uma regra

de produo.

Formalmente: Sendo G=(V, T, P, S) uma gramtica, uma Derivao

um par da relao de derivao : (VT)+ (VT)*, representado por: ou G

G indutivamente definida como segue:

Para toda regra de produo S , o seguinte par pertence a G : S G

Para todo par G de G, se uma regra de produo, ento o seguinte par pertence a G: G


Ex: Seja uma gramtica G=(V, T, P, N) definida por

V={N,D} T={0,1,2,...,9}

P={ND, NDN, D0|1|2|...|9}

Uma derivao da palavra 243 pode ser dada por:

NG (NDN)

DNG (D2)

2NG (NDN)

2DNG (D4)

24NG (ND)

24DG (D3)

243

Pergunta-se: Existem outras derivaes para a mesma palavra?


Derivao: Substituio de uma subpalavra de acordo com uma

regra de produo.

Sucessivos passos de derivao so definidos como segue:

* Fecho transitivo e reflexivo da relao , ou seja, zero ou

mais passos de derivaes sucessivos.

+ Fecho transitivo da relao , ou seja, um ou mais passos de

derivaes sucessivos.

i Exatos i passos de derivaes sucessivos, sendo i um nmero

natural.


Voltando ao exemplo anterior: G=(V, T, P, N) definida por

V={N,D} T={0,1,2,...,9}

P={ND, NDN, D0|1|2|...|9}

Como vimos, uma derivao da palavra 243 pode ser dada por:

N (NDN)

DN (D2)

2N (NDN)

2DN (D4)

24N (ND)

24D (D3)

243

Portanto, temos que: S * 243 ou S + 243 ou S 6 243


Def.: Seja G=(V, T, P, S) uma gramtica. A Linguagem Gerada

por G composta por todas as palavras de smbolos terminais

derivveis a partir de S.

Notao: L(G) ou GERA(G) = {w T* / S+w}

Ex:

Sendo V={N,D}

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

P={ND, NDN, D0|1|2|...|9}

G=(V, T, P, N) uma gramtica capaz de gerar qualquer nmero

natural vlido em uma linguagem de programao.


Analisando o exemplo anterior, onde:

G=(V, T, P, N) uma gramtica geradora de nmeros naturais.

V={N,D}

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

P={ND, NDN, D0|1|2|...|9}

A seguinte interpretao indutiva pode ser dada:

Base da Induo: todo dgito um nmero natural (regras ND e D0|1|2|...|9).

Passo de Induo: Se x um nmero natural, ento a concatenao de x com qualquer dgito tambm um nmero

natural (regra NDN).


Existem representaes alternativas para gramticas. Uma das mais comuns :

G = (V, , P, S), onde:

V contm todo o vocabulrio (todos os smbolos)

contm os smbolos terminais

P contm as produes

S o smbolo inicial

N = V - (corresponde ao conjunto de smbolos variveis da definio adotada

na disciplina)

Exemplo: a gramtica geradora de nmeros naturais vista no exemplo anterior

G = (V, , P, S)

V = {S, D, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9}

= {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}

P = {SD, SDS, D0|1|2|...|9}


Def.: Duas gramticas G1 e G2 so ditas equivalentes se ambas

geram a mesma linguagem, ou seja:

Gera (G1) = Gera(G2)

Obs: Em geral, adotaremos as seguintes convenes:

A, B, C, ..., S, T para smbolos variveis

a, b, c, ..., s, t para smbolos terminais

u, v, w, x, y, z para palavras com somente smbolos terminais

, , ... para palavras com smbolos terminais ou variveis


Consideremos as seguintes gramticas e respectivas linguagens:

G0 = ({S},{a,b},{SaS, SbS, S },S),

L0=Gera(G0)={a, b}*

G1 = ({S},{a,b},{SaS, SbS, S a|b},S),

L1=Gera(G1)={a, b}+

G2 = ({S,X},{a,b},{SaX, XaX, XbX, X},S),

L2 formada por cadeias iniciadas pelo smbolo a.

G3 = ({S,X},{a,b},{SaX, XaX, XbX, Xb},S),

L3 formada por cadeias iniciadas pelo smbolo a e terminadas por b.

G4 = ({S,X},{a,b},{SXbXbX, XaX, X},S),

L4 formada por cadeias que contenham exatamente dois smbolos b.

G5 = ({S,X},{a,b},{SbX, XaX, X},S),

L5 contm cadeias iniciadas com o smbolo b, sendo este o nico smbolo b

existente nessas cadeias.


Para cada uma, apresente um exemplo de sentena e de derivao associada

Consideremos as seguintes gramticas e respectivas linguagens:

L0=Gera(G0)={a, b}*, L1=Gera(G1)={a, b}

+, L2 formada por cadeias iniciadas

pelo smbolo a. L3 formada por cadeias iniciadas pelo smbolo a e terminadas por

b. L4 formada por cadeias que contenham exatamente dois smbolos b. L5 contm

cadeias iniciadas com o smbolo b, sendo este o nico smbolo b existente nessas

cadeias.

Analise as relaes de

incluso entre elas.


Uma gramtica G = (V, T, P, S) est bem formada se atender s

seguintes condies mnimas:

V, T, P devem ser conjuntos finitos e no vazios;

= V T

V T =

S V

Uma gramtica pode estar bem formada mas no gerar todas as

cadeias de uma linguagem. Exemplos: G = (V, T, P, S), onde:

a) V = {S, X}, T = {a, b}, P = {XaX | b}, S}

b) V = {S}, T = {a, b}, P = {SaS | b}, S}, mas G no gera bba


Hierarquia de Chomsky

Estudo sistemtico das linguagens formais teve forte impulso no final

da dcada de 1950 com publicao de dois artigos do linguista Noam

Chomsky.

Os artigos apresentavam resultados sobre a classificao hierrquica

das linguagens, conhecida como Hierarquia de Chomsky.

Tal hierarquia tem como mrito agrupar as linguagens em classes, de

tal forma que elas possam ser hierarquizadas segundo sua

complexidade relativa.

Como consequncia, conhecida a classe de uma determinada linguagem

pode-se antecipar propriedades fundamentais dessa linguagem, assim

como vislumbrar modelos de implementao mais adequados sua

realizao.


Hierarquia de Chomsky

Possui quatro classes distintas de linguagens: tipos 0, 1, 2 e 3

Cada tipo caracterizado por restries sobre o formato das produes

definidas pelo conceito geral de gramtica.

Tipo 0 Linguagens Recursivamente Enumerveis

ou Irrestritas

Tipo 1 Linguagens Sensveis ao Contexto

Tipo 2 Linguagens Livres de Contexto

Tipo 3 Linguagens Regulares


Hierarquia de Chomsky Linguagens Regulares (Tipo 3)

Tipo de linguagem mais simples da hierarquia.

Qualquer gramtica G=(V,T,P,S) geradora de linguagens regulares possui

produes que atendam s seguintes restries:

V

( T) ou ( V) ou ( T.V) ou ( = ), de forma no exclusiva ou

( T) ou ( V) ou ( V.T) ou ( = ), de forma no exclusiva

Exemplos:

G1=({S,A}, {0,1,2,3}, {S0S, S1S, SA, A2, A3}, S)

G2=({S,A}, {0,1,2,3}, {SS2, SS3, SA, A1, A0}, S)


Hierarquia de Chomsky Linguagens Livres de Contexto (Tipo 2)

Qualquer gramtica G=(V,T,P,S) geradora de linguagens livres de

contexto possui produes que atendam s seguintes restries:

V (s possuem um smbolo no terminal do lado esquerdo)

(V T)* (qualquer combinao de smbolos do lado direito)

Exemplo:

G3=({S}, {0,1}, {S0S1, S}, S)

G3 livre de contexto.


Hierarquia de Chomsky Linguagens Sensveis ao Contexto (Tipo 1)

Qualquer gramtica G=(V,T,P,S) geradora de linguagens sensveis ao

contexto possui produes que atendam s seguintes restries:

(VT)*.V. (VT)*

(VT)*

| | | | (O comprimento da cadeia do lado direito de cada produo seja no mnimo igual ao comprimento da cadeia do lado esquerdo)

Obs: No h possibilidade de reduzir o comprimento das formas

sentenciais durante derivaes em gramticas deste tipo.

Exemplo:

G4=({S,X,Y}, {a,b,c}, {SaXb, SaXa, Xabc, Xbcb}, S)

G4 sensvel ao contexto e no livre de contexto.


Hierarquia de Chomsky Linguagens Irrestritas (Tipo 0)

Qualquer gramtica G=(V,T,P,S) geradora de linguagens sensveis ao

contexto possui produes que atendam apenas a uma restrio:

(VT)*.V. (VT)* (lado esquerdo deve conter pelo menos um smbolo no terminal)

(VT)*

Exemplo:

G5=({S,X,Y}, {a,b,c}, {SaXb, SaXa, Xac, Xbc, X}, S)

G5 irrestrita e no sensvel ao contexto (devido s produes Xac,

Xbc, X): || ||

As gramticas G1, G2, G3 e G4 so todas irrestritas.


Hierarquia de Chomsky Linguagens, Gramticas e Reconhecedores

Tipo Classe de

Linguagem

Modelo de

Gramtica

Modelo de Reconhecedor

0 Recursivamente

Enumerveis

Irrestrita Mquina de Turing

1 Sensveis ao

Contexto

Sensvel ao

Contexto

Mquina de Turing com Fita

Limitada

2 Livres de

Contexto

Livre de

Contexto

Autmato de Pilha

3 Regulares Linear (direita

ou esquerda)

Autmato Finito

Obs: As propriedades, caractersticas estruturais e modelos de reconhecimento mais adequados para

cada uma das classes da Hierarquia de Chomsky sero estudados mais frente.


Atividades Prticas

Lista de Exerccios II - Completar

Leituras Recomendadas

Cap. 2 Paulo Blauth Menezes

Sees 2.1 a 2.3 Marcus Ramos

Sees 1.7 e 1.8 Papadimitriou

Seo 1.5 Hopcroft & Ullman


Documents

03_-_Linguagens_e_Gramaticas