• Finite-State Machines — 10 Sequential Logic Circuits (Design)
• Finite-State Automata — Pattern Recognition Languages and Compiler Design
• Turing Machines — An Abstract Model of a Digital Computer

Combinational Circuits

• The output depends only on the current input— no memory.

Sequential Circuits

• The output depends not only on the input but also on the state of the system, which is determined by previous processing
• In this sense, a sequential circuit has memory.

Finite-State Machine (FSM)

• A finite-state machine is an abstract model of a machine with a primitive internal memory; consists of:
  1. A finite set $\mathcal{I}$ of input symbols
  2. A finite set $\mathcal{O}$ of output symbols
  3. A finite set $\mathcal{S}$ of states. (current state นั่นแหละ)
  4. A next-state function $f$ from $\mathcal{S}\times\mathcal{I}$ into $\mathcal{S}$
  5. An output function $g$ from $\mathcal{S}\times\mathcal{I}$ into $\mathcal{O}$.
  6. An initial state $\sigma\in \mathcal{S}$
• We write $M$ = ($\mathcal{I, O, S, f, g, \sigma}$).

Example

• $\mathcal{I}=\{a,b\}$
• $\mathcal{O}=\{0,1\}$
• $\mathcal{S}=\{\sigma_0,\sigma_1\}$
• แล้วก็เขียน Next-state function, output function
  
• Then, $M$ = ($\mathcal{I, O, S, f, g, \sigma_0}$) is a finite state machine.
• Output จะเป็นอะไร ถ้า $aababba$— ก็ตอบเป็น Output เอาออกมาเขียน $0011001$

Finite-State Automaton (FSA)

• A variant of a finite state machine
• Used for defining a language
• Finite-State Automaton $A$ consists of:
  1. A finite set $\mathcal{I}$ of input symbols
  2. A finite set $\mathcal{S}$ of states. (current state นั่นแหละ)
  3. A next-state function $f$ from $\mathcal{S}\times\mathcal{I}$ into $\mathcal{S}$
  4. A subset $S_A$ of $S$ of accepting states
  5. An initial state $\sigma\in \mathcal{S}$
     
• $\sigma_1, \sigma_2$ are “accepting states”.

Language

• When a string is input to a finite-state automaton, we will end at ether an accepting state or a non-accepting state
• The status of ==this final state determines whether the string is accepted* by the finite-state automaton.==

• สมมติว่าอันนี้— The string $abaa$ is accepted by this finite-state automaton.

Example 1

Design a finite-state automaton that accepts precisely those strings over $\{ a, b \}$ that contain no a’s. (ให้ Design FSA ที่จะ Accept เฉพาะ String ไม่มี $a$)

• Idea ง่าย ๆ ก็คือให้มี 2 states
  • $A$: An $a$ was found
  • $NA$: No $a$’s were found.

• The state $NA$ is the initial state and the only accepting state. It is now a simple matter to draw the edges. Notice that the finite-state automaton correctly accepts the null string.

Example 2

Design a finite-state automaton that accepts precisely those strings over $\{ a, b \}$ that contain an odd number of $a$’s.

• Idea ของข้อนี้ก็คล้าย ๆ กัน เราจะมี 2 states
  • $E$: An even number of $a’$s was found.
  • $O$: An odd number of $a’$s was found.

• The initial state is $E$ and the accepting state is $O$.

Example 3 (In-class)

Design a finite-state automaton that accepts precisely the strings specified by the regular expression
$\huge{ab^*c^{+}(d|e)}$

• $*$ “Zero or more occurrences”
• $+$ “One or more occurrences”
• | “or”

• วิธีการทำ ==Start with “Shortest Happy Paths”== (consider shortest possible string)
  • In this case, it is ‘$acd$’ or ‘$ace$’
    
• แล้วก็ Complete Every (Input) States
  

Turing Machine

• Alan Turing (father of modern computer science)
• Turing machines are the most general models of computation; ‘they can do whatever a computer can do (any function เลยนะ)’

FSM vs Turing Machine

• Finite State Machines (FSMs) are valuable models for many kinds of computation, and have important practical applications, e.g., in the design of sequential circuits and pattern recognition algorithms.
• However, there are many important computations that FSMs cannot do.
  • Double an input—
  • No FSM can multiply a given input number by 2.
  • That is, it is impossible to construct an FSM that takes as input a string of 1s and produces as output a string of 1s twice as long.
  • The basic reason for this is that an FSM has, by definition, only finite memory and if the input string has too many 1s, the machine will lost count, and forget how many 1s to output.
  • บางครั้งเราก็ไม่รู้ว่าต้องมีกี่ States กันแน่
• FSMs are inadequate models for the most important kind of computational machine, the computer.
• FSA uses state to memorize things, no explicit memory! (This is a problem)
  • A computer with a 1 megabyte of memory— ต้องมี ${2^{2^{23}}}$ states เลยอะ

FSM + Explicit Memory (Two-way Tape Drive) = Turing Machine

• A Turing machine has a potentially infinite amount of memory.
• It is capable of performing any reasonable computation

Turing 2

• A Turing machine consists of two parts:
  1. A “read/write” tape head.
  2. A sufficiently long paper tape, ruled into squares.
     An operation performed by the “tape controller”
     can be one of three types:
      Move the head one square to the right.
      Move the head one square to the left.
      Cause the machine to halt. (This ends the computation.)