7 - Omega-regular languages

Question 1

formal definition of omega reg lang

Answer 1

Finite union of V.W^ω (looks like SLS)

more formally: There are reg languages V0, … ,Vn, W0, … , Wn ⊆ Σ* , with not only empty word in any W, so that

(0<=n)UVi.Wi^ω

Question 2

show that NBA iff omega-reg

Answer 2

NBA: finite automata, accepts infinite runs that reaches final state infinitely often

Equality proof:
something using the unions and using NFA with klenee*.. dunno, should be a easy proof

Question 3

DBA less expressive than NBA proof

Answer 3

counter example on trying to determinize NBA A with L(A) = {a,b}^ω : |w|b < ω (finitely many b’s )

consider word w = b.a^i1.ba^i2 …

there is a unique run r that

• has a common prefix with all ri on wi
• Every new prefix ri -> ri+1 yields another final state
• run r visits final state inifinitely often

Thus, contradicion, because ifinitely b

Question 4

omega-reg closure properties

Answer 4

concatenetion with left reg, union (by def), intersection (use automata)
not closed under concatenation (cant concatenate omega with omega)

Question 5

Rhamsey theorem

Answer 5

(about subgraph with edge colors)
basic ingredients
2 classes reg lang, composition etc

(V,E) complete infinite graph
Each edge E have a color in C
Then there is an infinite complete subgraph (V’,E∩P(V’)) with constant edge color

infinite ordered sequence of vertexes
induction
etc…

Question 6

Interection of NBA algorithm

Answer 6

Let A,B two NBA
Idea: Product automaton synchronized runs in A and B

Add counter to keep track of final state
Counter will be part of state:
Q = Qa x Qb x {0,1,2}
Q0 = (qa0,qb0,0)
Qf = Qa x Qb x {2}

–> defined as follows:
(qa,qb,i) -a-> (q’a,q’b,j) if qa -a-> q’a and qb-a->q’b and j:
1 if i = 0 and q’a ∈ Qaf or i = 1 and q’b ∉ Qbf
2 if i =1 and q’b ∈ Qbf
0 otherwise

Question 7

Complementation of NBA algorithm

Answer 7

à la Buchi (chapter 4.3.2):
Overview:
¬L(A) is a finite union of ω-concatenation of equivalence classes that are not in L(A).

Uses equivalence classes

Make boxes/matrix out of equivalent class

checkl all compositions [u][v]^ω from the matrix plus [empty] to check if they belong to L(A) or not.

in the end there will be something like

(eq1 U … U eqn).(eqx U … U .. eqy)^ω in L or ¬L

Equivalent class = set of all transition equivalent words (its reg)
transition equivalence for two words, means that they yield the same state changes

lemma
if w ∈ [u]~a,([v]~a)^ω and w ∈ L(A) then [u]~a,([v]~a)^ω ⊆ L(A)
(a.k.a if a word is made of the ω-concatenation of 2 equivalence classes, then this ω-concatenated classes are subset of L)

corollary:
w is in the complement of L(A), the ω-concatenteted classes are also

Buchi’s complementation theorem more formally:
¬L(A) = ∪ [u]~a . ([v]~a)^ω
([u]~a.([v]~a)^ω ∩ L(A) = ∅)