3 - Star-Free Languages

Question 1

how to play EF game

Answer 1

The game:

• Two players: Spoiler and duplicator
• Two words: v and w over Σ
• Number of rounds k ∈ N
• Potentially some existing edges

Per round:

• Spoiler selects positoin in v or w
• Duplicator selects position in other word and connects them by a line
• • Positions have same letters (preserve Pa)
• • new line doesn’t cross existing lines (preserve <)

Question 2

What are EF games good for?

Answer 2

cannot be distinguished by formulas and make it precise, make sure what k equivalence is and can write it down

Question 3

prove (aa)* not star*

Answer 3

Towards a contradiction, assume there is φ with L(φ) = (aa)*

Then φ has some quantifier depth k ∈ N

One can check that duplicator wins the game
Gk(a^2k, a^2k+1)
Hence, the two words cannot be distinguished by φ.

This is a contradiction to a^2k ∈ L(φ), but a^2k+1 ∉ L(φ).

Hence, formula φ cannot exist.

Question 4

prof of EF theorem (overall structure)

Answer 4

induction in one direction:
-To add an existential quantifies allows to add one round in the game

Question 5

explain why star* not in REG

Answer 5

weaker (cannot write aa*)

Question 6

example of star* lang and write as *free exp

Answer 6

(ab)* = Σ* \ b.Σ* \ Σ*.aa.Σ* \ Σ*.bb.Σ* \ Σ* . a
that means:
All words removing:
- words starting with b
- words with 2 consecutive a or b
- words ending with a