pnposgrad2-34

Prévia do material em texto

<p>04/03/2010</p><p>34</p><p>Linguagem Gerada pelas Linguagem Gerada pelas</p><p>Redes de PetriRedes de Petri</p><p>λ</p><p>a b</p><p>p0</p><p>p1</p><p>p2</p><p>L(RL) = {a,a,a, ..., RL</p><p>Linguagem Gerada pelas Linguagem Gerada pelas</p><p>Redes de PetriRedes de Petri</p><p>λ</p><p>a b</p><p>p0</p><p>p1</p><p>p2</p><p>L(RL) = {a,a,a, ...,b RL</p><p>Linguagem Gerada pelas Linguagem Gerada pelas</p><p>Redes de PetriRedes de Petri</p><p>λ</p><p>a b</p><p>p0</p><p>p1</p><p>p2</p><p>L(RL) = {a,a,a, ...,b,b RL</p><p>Linguagem Gerada pelas Linguagem Gerada pelas</p><p>Redes de PetriRedes de Petri</p><p>λ</p><p>a b</p><p>p0</p><p>p1</p><p>p2</p><p>L(RL) = {a,a,a, ...,b,b,b}</p><p>L(RL) = {anbn | n≥0}</p><p>RL</p><p>Expressividades das Expressividades das</p><p>Linguagens Geradas pelas RdPLinguagens Geradas pelas RdP</p><p>Redes de PetriRedes de Petri ×× Automatos FinitosAutomatos Finitos</p><p>�� A expressividade das linguagens RdP é superior A expressividade das linguagens RdP é superior</p><p>ao das geradas pelos automatos finitos.ao das geradas pelos automatos finitos.</p><p>�� ProvaProva</p><p>–– Mostrar que Mostrar que qualquer Automato Finitoqualquer Automato Finito podepode ser ser</p><p>representado por uma RdPrepresentado por uma RdP. Portanto, as linguagens geradas . Portanto, as linguagens geradas</p><p>pelos Automatos Finitos podem ser geradas pelas RdP.pelos Automatos Finitos podem ser geradas pelas RdP.</p><p>–– Mostrar que Mostrar que há RdP que não podehá RdP que não pode ser representada por umser representada por um</p><p>Automato FinitoAutomato Finito. Portanto, nem toda linguagem gerada por . Portanto, nem toda linguagem gerada por</p><p>uma RdP pode ser representada pela linguagem geradas uma RdP pode ser representada pela linguagem geradas</p><p>pelos Automatos Finitos.pelos Automatos Finitos.</p><p>Expressividades das Expressividades das</p><p>Linguagens Geradas pelas RdPLinguagens Geradas pelas RdP</p><p>�� Automato FinitoAutomato Finito</p><p>AF =AF =(S,s(S,s00,E,f),E,f)</p><p>S={sS={s00,s,s11}}</p><p>E={e}E={e}</p><p>f:sf:s00 ×× e e →→ ss11</p><p>s0</p><p>S0 S1</p><p>e</p><p>�� Rede de PetriRede de Petri</p><p>R=(P,T,I,O)R=(P,T,I,O)</p><p>PP={s={s00,s,s11}}</p><p>T={e}T={e}</p><p>I(e)={sI(e)={s00}}</p><p>O(e)={sO(e)={s11}}</p><p>s1</p><p>e</p>