Differences

This shows you the differences between two versions of the page.

--- lat:homework [2009/11/27 22:52]
barbara.jobstmann
+++ lat:homework [2009/12/06 12:32] (current)
radu.iosif
@@ Line 3: / Line 3: @@
 ===== 02.10.2009 =====
- Consider the automata construction from proof of the Myhill-Nerode theorem for a language L. Prove
+Consider the automata construction from proof of the Myhill-Nerode theorem for a language L. Prove
   * (a) the constructed automaton A is the minimal automaton (in the number of states) that recognizes L;
   * (b) any minimal automaton recognizing L is isomorphic to A.
@@ Line 9: / Line 10: @@
 ===== 06.11.2009 =====
      - Given a reachability game (G,F), give an algorithm that computes the 0-Attractor(F) set in time O(|E|).
      - Consider the game graph shown in below and the following winning conditions: a) Occ(ρ) ∩ {1} ≠ ∅ and b) Occ(ρ) ⊆ {1,2,3,4,5,6} and c) Inf(ρ) ∩ {4,5} ≠ ∅. Compute the winning regions and corresponding winning strategies showing the intermediate steps (i.e., the Attractor and Recurrence sets) of the computation.\\ {{hw1.gif|Figure 1}}
@@ Line 18: / Line 20: @@
 ===== 13.11.2009 =====
      - Consider the game graph shown below.  Let the winning condition for Player 0 be Occ(ρ)={1,2,3,4,5,6,7}
         - Find the winning region for Player 0 and describe a winning strategy
@@ Line 25: / Line 28: @@
 ===== 27.11.2009 =====
      - Consider the game graph below and the Muller condition F={{2,4,5,7},{1,2,3,4,5,6,7}}. Find an automaton winning strategy for Player 0 in the Muller game with as few states as possible and show that any other automaton strategy with less states is not winning for Player 0.\\ {{hw4.gif}}
-     - Consider the game shown on page 6 of {{:slide10.pdf}}. We propose the following "latest appearance queue" (LAQ) strategy for Player 0, initializing the queue with s<sub>1</sub>s<sub>2</sub>s<sub>3</sub>s<sub>4</sub>, (1) add the current state at the front of the LAQ and delete the last state (2) move to the state t<sub>i</sub> whose number i is the number of different states in the current LAQ, e.g., for the sequence of states s<sub>1</sub>, s<sub>3</sub>, s<sub>3</sub>, s<sub>4</sub>, s<sub>1</sub>,... we obtain the following sequence of LAQs: s<sub>1</sub>s<sub>2</sub>s<sub>3</sub>s<sub>4</sub>, s<sub>1</sub>s<sub>1</sub>s<sub>2</sub>s<sub>3</sub>, s<sub>3</sub>s<sub>1</sub>s<sub>1</sub>s<sub>2</sub>, s<sub>3</sub>s<sub>3</sub>s<sub>1</sub>s<sub>1</sub>, s<sub>4</sub>s<sub>3</sub>s<sub>3</sub>s<sub>1</sub>,s<sub>1</sub>s<sub>4</sub>s<sub>3</sub>s<sub>3</sub>,...     Decide wheater the new LAQ strategy is a winning strategy for Player 0. Prove this or give a counter-example.
+     - Consider the game shown on page 6 of {{:slide10.pdf}}. We propose the following "latest appearance queue" (LAQ) strategy for Player 0, initializing the queue with s<sub>1</sub>s<sub>2</sub>s<sub>3</sub>s<sub>4</sub>,
+        - add the current state at the front of the LAQ and delete the last state
+        - move to the state t<sub>i</sub> whose number i is the number of different states in the current LAQ,\\ e.g., for the sequence of states s<sub>1</sub>, s<sub>3</sub>, s<sub>3</sub>, s<sub>4</sub>, s<sub>1</sub>,... we obtain the following sequence of LAQs: s<sub>1</sub>s<sub>2</sub>s<sub>3</sub>s<sub>4</sub>, s<sub>1</sub>s<sub>1</sub>s<sub>2</sub>s<sub>3</sub>, s<sub>3</sub>s<sub>1</sub>s<sub>1</sub>s<sub>2</sub>, s<sub>3</sub>s<sub>3</sub>s<sub>1</sub>s<sub>1</sub>, s<sub>4</sub>s<sub>3</sub>s<sub>3</sub>s<sub>1</sub>,s<sub>1</sub>s<sub>4</sub>s<sub>3</sub>s<sub>3</sub>,...\\ Decide wheater the new LAQ strategy is a winning strategy for Player 0. Prove this or give a counter-example.
      - Let A=(S,s<sub>0</sub>,T,p) be a parity automaton with p:S -> {1,..,k}. Construct a Streett automaton B=(S,s<sub>0</sub>,T,F) equivalent to A that has the same transition structure as A. (i.e., find a suitable set of Streett pairs (F_i,E_i))
+===== 6.12.2009 =====
+ - Exam-like problems on automata and Presburger Arithmetic {{homework.pdf}}