Baixe o app para aproveitar ainda mais
Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original
* MAJS - FTC Linguagem Conjunto de strings/sentenças. String/sentença: uma seqüência finita de elementos construída a partir de uma base. Alfabeto (S): conjunto de símbolos que permitem derivar os strings da linguagem. Convenções letras a, b, c... são usadas para representar os elementos de um alfabeto. p, q, u, v, w, x, y, z são usadas para representar strings gerados a partir de um alfabeto. * MAJS - FTC Fecho - Estrela de Kleene Considere S um alfabeto. S* representa o conjunto de todos os strings gerados por S. Formalmente: base: l Î S*. passo recursivo: se w Î S* e a Î S então wa Î S*. fechamento: w Î S* somente se puder ser obtido a partir de l com um nº finito de aplicações do passo recursivo. * MAJS - FTC Exemplo Se S = { a } então: S* = { l , a, aa, aaa, ... }. Se S = { while, >, id } então: S* = { l, while, while > id >, while id > id, ... }. Nota: se S ¹ Æ , então S* contém infinitos elementos. se S = Æ , então S* contém apenas { l }. * MAJS - FTC Propriedades e Operações com strings O tamanho/comprimento de um string w - length(w): nº de aplicações do passo recursivo para se obter w. Exemplo: se S = {a, b, c}, os elementos de S* incluem: tamanho 0: l tamanho 1: a b c tamanho 2: aa ab ac ba bb bc ca cb cc * MAJS - FTC Propriedades e Operações com strings Seja u, v Î S*. A concatenação de u e v, escrita uv, é uma operação binária em S*: base: se length(v) = 0, então v = l e uv = u. passo recursivo: se length(v) = n > 0, então v = wa e uv = (uw)a (length(w) = n – 1, a Î S). * MAJS - FTC Propriedades e Operações com strings Exemplo: u = ab, v = ca, w = bb uv = abca vw = cabb (uv)w = abcabb u (vw) = abcabb Concatenação é associativa? (uv)w = u(vw). * MAJS - FTC Teorema Considere u, v, w Î S*: (uv)w = u(vw). Prova: por indução no comprimento do string w. base: length(w) = 0, então w = l e (uv)w = (uv)l = uv. Analogamente, u(vw) = u(vl) = u(v) = uv. hipótese: assuma que (uv)w = u(vw) w, length(w) £ n. passo indutivo: provar que (uv)w = u(vw) Ö w, length(w) = n + 1. * MAJS - FTC Considere w tal string: w = xa, length(x) = n, a Î S. (uv)w = (uv)xa = ((uv)x)a “definição de concatenação” = (u(vx))a “hipótese” = u((vx)a) “definição de concatenação” = u(v(xa)) “definição de concatenação” = u(vw) C.Q.D. * MAJS - FTC Notas Concatenação não é comutativa. x é um substring de y se $ x , v, z I y = zxv. x é dito prefixo de y se z = l, ou seja, y = xv. x é dito sufixo de y se v = l, ou seja, y = zx. * MAJS - FTC Definição Considere w S*. O reverso de w, denotado wR, é definido por: base: length(w) = 0. Então w = l e lR = l. passo recursivo: se length(w) = n ³ 1, então w = ua e wR = auR para length(u) = n - 1, a Î S. * MAJS - FTC Teorema Considere x, y Î S*: (xy)R = yR xR. Prova por indução no comprimento de y. base: se length(y) = 0, então y = l e (xy)R = (xl)R = xR. Analogamente yR xR = lR xR = xR. hipótese: assuma que (xy)R = yRxR Ö length(y) £ n. passo indutivo: provar que (xy)R = yR xR para length(y) = n+1. * MAJS - FTC Considere y tal string: y = wa, length(w) = n, a Î S. (xy)R = (x (wa))R = ((xw) a)R associatividade = a(xw)R definição de reverso = a(wRxR) hipótese = (awR)xR associatividade = (wa)RxR definição de reverso = yRxR C.Q.D. * MAJS - FTC Linguagem Na realidade, certas restrições são impostas aos strings: propriedades - sintaxe da linguagem. Nova definição: Uma linguagem L é um subconjunto de S* (L S*). * MAJS - FTC Operações A concatenação da linguagem X e Y, denotada XY, é a linguagem XY = {xy I x Î X e y Î Y} Exemplo: X = {a, b, c} Y = {abb, ba} XY = {aabb, aba, babb, bba, cabb, cba} X0 = { l } X1 = {a, b, c} X2 = {aa, ab, ac, ba, bb, bc, ca, cb, cc} * MAJS - FTC Operações Considere X S*: X* = X+ = Fecho Fecho positivo * MAJS - FTC Especificação de Linguagem Requer uma descrição não ambígua dos strings Seja S = { a, b } e L S* a linguagem de todos os strings que contém bb. Ambigüidades: uma só ocorrência de bb? várias ocorrências de bb? no mínimo uma ocorrência de bb ? * MAJS - FTC Especificando Linguagens Considere S = { a, b }. L = {a, b}* {bb} {a,b}* A linguagem contêm pelo menos uma ocorrência de bb. L = {aa} {a, b}* È {a, b}* {bb} A linguagem que possui prefixo aa ou sufixo bb. * MAJS - FTC Especificando Linguagens Considere S = { b } e L1 = {bb}, L2 = {l, bb, bbbb}. L1* e L2* - precisamente a linguagem de todos os strings consistindo de um número par de b’s. L1* = {l, bb, bbbb, bbbbbb, ... } L2* = {l, bb, bbbb, bbbbbb, ... } * MAJS - FTC Um conjunto é dito regular se pode ser gerado, a partir de S, usando apenas as operações de fecho, união e concatenação. Definição recursiva: base: Æ, { l } e { a } Ö a Î S , são conjuntos regulares. passo recursivo: se X, Y são conjuntos regulares, então XÈY, XY, X* são regulares. Conjuntos Regulares * MAJS - FTC O conjunto cujos strings começam e terminam em a e contêm pelo menos um b. {a} {a, b}* {b} {a, b}* {a} Observação: fecho tem a mais alta prioridade seguida da concatenação e união. Exemplo * MAJS - FTC Abreviação para conjuntos regulares. Definição recursiva: base: Æ, l e a Ö a Î S, são expressões regulares em S. passo recursivo: se u e v são expressões regulares, então uÈv, uv e u* são expressões regulares. Expressão Regular * MAJS - FTC {a} {a, b}* {b} {a, b}* {a} = a (a È b)* b (a È b)* a {a, b}* {bb} {a, b}* = (a È b)* bb (a È b)* Nota: (a I b)* bb (a I b)* = (a È b)* bb (a È b)* x+ denota xx* x2 denota xx, x3 denota x2x ... Mostre que { bawab I w Î {a, b}* } é regular em S = {a, b}. Exibir a cada passo a expressão regular correspondente. Exemplo * MAJS - FTC Identidades 1) Æ w = w Æ = Æ 2) l w = w l = w 3) Æ* = l 4) l* = l 5) w È y = y È w 6) w È Æ = w 7) w È w = w 8) w*w* = w* 9) (w*)* = w* 10) w*w = ww* = w+ * MAJS - FTC Identidades 11) w (x È y) = wx È wy 12) (x È y) w = xw È yw 13) (wy)* w = w (yw)* 14) (w È y)* = (w* È y)* = w* (w È y)* = (w È yw*)* = (w* y*)* = w* (yw*)* = (w*y)* w* * MAJS - FTC Aplicação Mostre que: a* (a* ba* ba* )* = a* (ba* ba*)*. b* (ab+)* È b* (ab+)* a = (b È ab)* (l È a). Verifique se acabacc e bbaaacc estão no conjunto representado por c* (b È (ac*))*. Nota: É importante observar que existem linguagens que não podem definidas por expressões regulares: { anbn I n ³ 0 }.
Compartilhar