Protocol questions

Question 1

regex to NFA?

Answer 1

Rules for each operation

example

Question 2

Overview of all language classes of the semester

Answer 2

• Finite words: Sigma *, REG, Star-free
• Infinite words: Sigma ^ omega, omega-REG, LTL languages
• Finite tree languages
• Infinite tree / parity games

Question 3

What are the constructs to to describe regular languages?

Answer 3

NFA, regex, WMSO

Question 4

NFA to regex?

Answer 4

ardens lemma: proof in detail, idea for design through system of equations

Question 5

WMSO to NFA?

Answer 5

Buchi II

Only rough idea (Alphabet extension) and the automaton for x <y

feature (projection) + argument for projection

Question 6

For star-free languages, we had such games, what was that?

Answer 6

• Ehrenfeucht-Fraissé Games explains what they are used (for illustrative partial isomorphisms),
• EF theorem (k-equivalence), rough idea of ​​the proof

Question 7

Application of EF theorem?

Answer 7

(aa) * non-star-free, complete proof

Question 8

explain WMSO name + signature definition etc

Answer 8

Weak - Finite
Monadic - ???
Second order - Set variables

Question 9

Automaton model infinite words?

Answer 9

Büchi automata

Question 10

Counterexample for determinability of Buchi automata?

Answer 10

(a+b)^omega with finitely many b’s

not in L (DBA)

Question 11

Omega-REG closed under intersection?

Answer 11

Yes, {0,1,2}-counter design

Question 12

Idea of ​​proof complementation NBA?

Answer 12

• Definition ~
  
  • Of finite index
  • All classes in REG
  • UV ^ omega always in L (A) or completely outside
  • UV ^ omega cover all sigma omega ^
    To do this: Ramsey’s theorem (without proof)

Question 13

What is a push-down system?

Answer 13

Stack-based system model

Question 14

How to Check if possible in accepting BPDS Run?

Answer 14

Analysis by terms (1) and (2),

• Translation in (1 ‘) and (2’) (statements with pre *)
• Very rough idea of ​​the pre * Calculation

Question 15

What we had for automata on trees?

Answer 15

BUTA = DBUTA = TDTA > DTDTA

Question 16

Word problem for hedge automata?

Answer 16

Double on-the-fly determinisieren

Question 17

how do we poove regex equivalent to NFA?

Answer 17

=> exclusiveness v. nfa with operations from def reg..

<= Build reg expression of nfa to, for example.

Question 18

Formal prove of omega-reqular equivalence to NBA

Answer 18

• Showing NBA over complete complementary (define association with the [u] [v] ^ omega nich in L (A)), proves this:
  
  • Def. of u ~ v
  • show [u] requlär
  • f.a. w: w in [u][v]^omega
  • Endl many ÄK
  • ÄK completely or completely not in L (A)

Question 19

NFA to WMSO?

Answer 19

Buchi I

5 step construction

Question 20

define omega regular language

Answer 20

TODO

Question 21

NBA to omega-reg?

Answer 21

TODO

Question 22

Omega-reg closure properties?

Answer 22

TODO

Question 23

Complement of Omega-reg: construction plus all correctness arguments:

Answer 23

Finiteness of classes
sufficient fine separation
Every word in omega regular class association (+ Ramsey)