Identificando Linguagens Não Regulares

  • Published on
    05-Jan-2016

  • View
    19

  • Download
    0

Embed Size (px)

DESCRIPTION

Identificando Linguagens No Regulares. Linguagens regulares podem ser finitas; Uma linguagem regular sss, em processando qualquer cadeia, a informao a ser armazenada em qualquer estgio estritamente limitada. Exemplo: A linguagem L={ a n b n |n 0} no regular. - PowerPoint PPT Presentation

Transcript

<ul><li><p>Identificando Linguagens No Regulares </p><p>Linguagens regulares podem ser finitas;Uma linguagem regular sss, em processando qualquer cadeia, a informao a ser armazenada em qualquer estgio estritamente limitada.</p></li><li><p>Exemplo: A linguagem L={ an bn|n0} no regular.</p><p>Suponha que L regular. Ento existe um AFD M=(Q, {a,b},S,q0,F) que a reconhe-ce. Seja k o nmero de estados de M. Consideremos o funcionamento de M na entrada anbn, onde n k</p></li><li><p> aaaaaaaaaabbbbbbbbbb q 0 n n r</p><p>Como nk, deve existir algum estado p tal que M est em p mais de uma vez enquanto percorrendo a parte inicial da sequncia de as (princpio da casa dos pombos).</p></li><li><p>Quebre anbn em 3 pedaos u, v, w onde v a cadeia de as percorrida entre duas ocorrncias de p. aaaaaa aaaa bbbbbbbbbb q0 u p v p w r</p></li><li><p>Seja j=|v|&gt;0 (j=4, no exemplo) * (q0,u) = p * (p,v) = p * (p,w) = r F</p><p>Logo podemos remover v o que resultaria numa cadeia ser erroneamente aceita:</p></li><li><p> *(q0,uw) = *(*(q0,u),w) = *(p,w) = r F aaaaaa bbbbbbbbbb q0 p r u w </p></li><li><p>Lema do Bombeamento (Pumping Lemma)</p><p>TEOREMA: Seja L uma linguagem regular. Ento existe um inteiro positivo m, tal que w L com |w| m pode ser decomposta como w= xyz com |xz|m e |y|1 tal que wi=xyiz est tambm em L para todo i = 0,1,2, ...</p></li><li><p>Prova Sejam q0, q1,, qn os estados do AFD que reconhece L. Agora tome uma cadeia w L tal que |w|=km=n+1. Seja q0,qi,qj, ,qf o conjunto de estados do autmato no reconhe-cimento de w. Como esta cadeia tem no mnimo n+1 entradas, pelo menos um estado deve ser repetido, e tal repetio no deve comear aps o n-simo movimento. </p></li><li><p>Portanto, a sequncia deve ter a seguinte forma q0,qi,qj, ,qr, ,qr, , qf indicando que devem existir subcadeias x, y, z de w tal que *(q0,x)=qr, *(qr,y)=qr, *(qr, z)=qf com |xz| n+1 = m e |y|1.Donde segue imediatamente que *(q0,xz)=qf, *(q0, xy2z)=qf, *(q0,xy3z)=qf ... q.e.d</p></li><li><p>GramticasGramticauma ferramenta comum e poderosa para definir linguagens.Definio: Uma gramtica G uma qudrupla G=(V, T, S, P) onde:V um conjto finito de variveis ou smbolos no-terminais;T um conjunto finito de smbolos terminais;S V um smbolo especial chamado de smbolo inicial ou varivel de incio;P um conjunto finito de produes</p></li><li><p>As regras de produo so da forma xy, onde x um elemento de (VT)+ e y est em (VT)*. As produes so aplicadas como segue: dada uma cadeia w da forma w=uxv, dizemos que a produo aplicvel a esta cadeia e podemos us-la para trocar x por y, obtendo assim uma nova cadeia z=uyvIsto escrito por wz (w deriva z ou z derivada de w ou z deriva de w). </p></li><li><p>Se w1w2...wn, dizemos que w1 deriva wn e escrevemos w1*wn * indica que foi tomado um nmero no-especificado de etapas (inclu-indo zero) para derivar wn de w1. Logo w*w sempre se d.Para indicar que pelo menos uma produo foi aplicada, escreve-mos w+v</p></li><li><p>Aplicando as regras de produo em ordens diferentes, uma gramtica pode gerar muitas cadeias. O conjunto de todas tais cadeias a linguagem definida ou gerada pela gramtica.</p></li><li><p>Linguagem GeradaDefinio: Seja G = (V, T, S, P) uma gramtica. Ento o conjun-to L(G) = {wT* | S*w} a linguagem gerada por G. Se w L (G), ento a sequncia Sw1w2 wnw uma derivao da sentena (ou palavra) w.</p></li><li><p>ExemploG = onde P dado por SaSb e SEnto SaSb aaSbb aabb Logo podemos escrever S*aabb Uma gramtica define completamen-te L(G), porm pode no ser fcil obter uma descrio explcita da linguagem a partir da gramtica.Neste exemplo, no entanto, no difcil conjecturar que L(G)={anbn|n0}</p></li><li><p>Gramticas RegularesUma gramtica G = diz-se linear direita se todas as produes so da forma A xB ou Ax onde A, B V, e x T*.e linear esquerda se todas as produes so da forma AxB Ax </p></li><li><p>Uma gramtica regular uma que ou linear direita ou linear esquerda.Observe que numa gramtica regular no mximo aparece uma varivel no lado direito de qualquer produo. Alm disso, essa varivel est mais esquerda ou mais a direita de qualquer produo.</p></li><li><p>ExemplosG1 = ({s},{a,b},S,P1), P1: SabS|a linear direita.SabS ababS ababaL (G1) a linguagem L((ab)*a)G2 = ({S,S1,S2},{a,b},S,P2), com produes SS1ab, S1S1 ab|S2, S2a linear esquerda.S S1abS1ababS2ababaababL(G2) a linguagem L(a(ab)*)</p></li><li><p>Cuidado!A gramtica G=({S,A,B},{a,b},S,P) com produes SA AaB| BAbno regular!</p></li><li><p>Gramticas Lineares Direita Geram Linguagens Regulares</p><p>Construir um AFND que simula as derivaes de uma gramtica linear direita. AbcDAbcdE por DdEO AFND vai do estado D para o estado E quando o smbolo d for encontrado.</p></li><li><p>Teorema. Seja G = (V, T, S, P) uma gramtica linear direita. Ento L(G) uma linguagem regular.Prova. Assumir V={V0,V1,,Vp}, com S=V0 e que temos produ-es da forma V0v1Vi, Viv2Vj, , ou Vnvl, </p></li><li><p>Se w uma cadeia em L(G), ento por causa das formas das produes em G, a derivao deve ter a forma da equao acima. V0 v1Vi v1v2Vj * v1v2 vk Vn v1v2 vk ve = w</p></li><li><p>O autmato a ser construdo repro-duzir a derivao, consumindo cada um desses vs.O estado inicial do autmato ser ro-tulado V0, e para cada Vi existir um estado no final rotulado Vi.Para cada Via1a2amVj definire-mos tal que *(Vi,a1a2am)=VjPara cada Via1a2am , *(Vi,a1a2am)=Vf, onde Vf um estado final. Os estados intermedi-rios no so de interesse e podem ser dados rtulos arbitrrios. </p></li><li><p> a1 a2 am ... representa Via1a2amVj</p><p> a1 a2 am </p><p>representa Via1a2amvivjvfvi</p></li><li><p>Suponha agora que w L (G). No AFND existe uma aresta de V0 a Vi rotulada v1, de Vi a Vj rotulada v2, etc., tal que Vf *(V0, w), e w aceita por M. </p><p>Inversamente, suponha que w aceita por M. Para aceitar w o autmato tem de passar pela sequncia de estados V0, Vi,,Vf usando caminhos rotulados v1,v2,,vl</p></li><li><p>Portanto, w deve ter a forma w=v1v2vkvl e a derivaoV0v1Viv1v2Vj*v1v2vkVk v1v2vkvl possvel. Logo W est em L(G), e assim o teorema est provado.</p></li><li><p>ExemploConstruir um autmato que aceita a linguagem gerada pela gramtica V0aV1 V1abV0 |b </p><p>comeamos do grafo de transio com vrtices V0, V1 e Vf.</p></li><li><p>A primeira regra de produo cria uma aresta rotulada a entre V0 e V1. Para segunda regra, precisamos introduzir um vrtice adicional tal que existe um caminho rotulado ab entre V1 e V0.</p></li><li><p>Finalmente, precisamos adicionar uma aresta rotulada b entre V1 e Vf</p><p>A linguagem gerada pela gramtica e reconhecida pelo autmato a linguagem regular L ((aab)*ab)v0v1vfbbaav2</p></li><li><p>Gramticas Lineares Direita Para Linguagens RegularesComeamos agora do AFD para a linguagem e invertemos a construo do teorema anteriorOs estados do AFD tornam-se as variveis da gramtica, eOs smbolos que causam as transies tornam-se os terminais nas produes</p></li><li><p>Teorema: Se L uma linguagem regular sobre o alfabeto , ento existe uma gramtica linear direita G = (V,,S,P) tal que L = L(G).</p></li><li><p>Prova: Seja M = (Q,,,q0, F) um AFD que aceita L. Assumiremos que Q = {q0,q1,, qn) e = {a1, a2,am}.Vamos construir uma gramtica linear direita G = (V, , S, P) com V = {q0, q1,,qn} e S = q0. Para cada transio (qi, aj) = qk de M, colocamos em P a produo qiajqk. Alm disso, se qk est em F, acrescentamos a P a produo q.</p></li><li><p>Primeiro mostramos que G defini-da dessa maneira pode gerar toda cadeia em L. Considere w L da forma w = aiajakal.Para M aceitar essa cadeia ele deve se movimentar via (q0, ai) = qp, (qp, aj) = qr, ... (qs, ak) = qt, (qt, al) = qf F</p></li><li><p>Por construo, a gramtica ter uma produo para cada um desses s. Portanto, podemos fazer a derivao q0aiqpaiajqr*aiajakqt aiajakalqfaiajakal com a gramtica G, e w L(G).</p></li><li><p>Inversamente, se w L(G), ento sua derivao deve ter a forma da equao acima, mas isto implica que (q0, ai, ajakal) = qf, completando a prova.q.e.d.</p></li><li><p>Equivalncia Entre Linguagens Regulares E Gramticas RegularesOs resultados anteriores estabele-cem a conexo entre linguagens regulares e gramticas lineares direita.Podemos fazer uma conexo anlo-ga entre linguagens regulares e gramticas lineares esquerda, mostrando assim, a equivalncia de gramticas e linguagens regulares.</p></li><li><p>Teorema.</p><p>Uma linguagem regular se e somente se existe uma gramti-ca regular G tal que L = L(G).</p></li></ul>

Recommended

View more >