martes, 6 de noviembre de 2012

Tarea 10: expresión ω-regular & NBA

Para esta tarea tenemos que inventar una expresión regular ω y hacer el diagrama del automata no determinista de Büchi.

Una expresión ω-regular G en ∑ tiene la forma:
G = E1F1 ω + ... + En Fn ω 

Donde E1, ... , En y F1, ... , Fn son expresiones regulares de ∑ y Λ∉L(Fi) para todas i.

Un lenguaje de G es:
L(G) = L(E1)L(F1)ω U ... U L(En)L(Fn)ω


Por lo tanto, pongo la siguiente expresión.

(A+B)+(AB)ω

 




 Este sería mi NBA.

 Bibliografía.
  • Concurrency - Slides - Link
  • Principles of Model Checking - Christel Baier - Link
  • Automata - Berndt Farwe - Link

1 comentario: