Finite-State Automata

Has formal languages course as a prerequisite: memcode.com/courses/158.

11 flashcards · Mathematics · by lakesare

1. Combinational logic VS sequential logic?

   Combinational logic: output is a pure function of the present input only. Sequential logic: logic circuit whose output depends not only on the present value of its input signals but on the input history. Sequential logic has state.

2. What logic type is finite-state automaton concerned with?

   Sequential logic, because it has state.

3. Name 5 objects finite-state automaton A consists of.

   1. Finite set I of input symbols (input alphabet); 2. Finite set S of states the automaton can be in; 3. Initial state s0; 4. Set of accepting states; 5. Next-state function N: S × I → S that associates a “next-state” to each ordered pair consisting of a “current state” and a “current input.” For each state s in S and input symbol m in I, N(s, m) is the state to which A goes if m is input to A when A is in state s.

4. Here is a transition diagram for a state machine A. What are the states of A? What are the input symbols of A? What is the initial state of A? What are the accepting states of A? Determine N(s1, 1). Construct the annotated next-state table for A.

   s0, s1, s2 [since these are the labels of the circles] 0, 1 [since these are the labels of the arrows] s0 [since the unlabeled arrow points to s0] s2 [since it's the only state marked by a double circle] N(s1, 1) = s2 [since there is an arrow from s1 to s2 labeled 1]

5. Consider this next-state table: What's N(U, c)?

   N(U, c) = Y. Which means that given state U and input c, next-state function will return state Y.

6. Define a language accepted by A L(A).

   It's a set of all strings (made of input symbols) that drive A from the s0 into each of the accepting states.

7. Here is a transition diagram for a state machine A. To what states does A go if the symbols of the following strings are input to A in sequence, starting from the initial state? (i) 01 (ii) 0011 (iii) 10101 Which of those strings send A to an accepting state? What is the language accepted by A? Is there a regular expression that defines the same language?

   01: s1, 0011: s0, 10101: s2 Those that send A to a state s2. L(A) = { all strings that end in 01 } L(A) = (0 | 1)∗01

8. How is next-state function different from eventual-state function? Express both as (f: X -> Y).

   next-state: N: S × I → S eventual-state: N*: S × I* → S next-state f(state, input) → state eventual-state f(state, string_of_inputs) → state Where - S: set of all states, I: set of all inputs.

9. Here is a transition diagram for a state machine A. Find and explain N∗(s1, 10110).

   N* denotes an eventual-state function. We are given a string of inputs 10110, and have to feed it into our state machine starting from s1. N∗(s1, 10110) = s1

10. Denote language accepted by A L(A) in set notation.

    L(A) = { w ∈ I∗ | N∗(s0, w) = saccepting } Where - I: set of all inputs (alphabet) I*: set of all strings from these inputs (language) w: one of those strings N*: eventual-state function s0: initial state

11. What does it mean for a state machine to accept a language?

    It means that every string from this language (a set of strings), if fed to a state machine starting from s0, will lead it to the accepting state. There can be only one L(A).