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 = E₁F₁ ^ω + ... + E_n F_n ^ω 

Donde E₁, ... , E_n y F₁, ... , F_n son expresiones regulares de ∑ y Λ∉L(Fi) para todas i.

Un lenguaje de G es:

L(G) = L(E₁)L(F₁)^ω U ... U L(E_n)L(F_n)^ω

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