TULA

TULA

Dayeong Kang

Basics of automata theory

There are three keywords to understand automata theory: language, grammar, and automata.

Languages and Grammars

There are a lot of languages in the world: I will use English to explain its definition.

  1. Alphabet: a finite and nonempty set $\sum$ of symbols which are a, b, c, and so on
  2. String: a finite sequence of symbols
    • Σ*: a set of strings
    • Σ+ = Σ* - $\lambda$
    • Empty: $\lambda$ ($\left | \lambda \right | = 0$)
    • $w = w\lambda = \lambda w$
    • $w^0 = \lambda$
  3. Operations
    • Concatenation: $w$ = abc, $v$ = xyz → $wv$ = abcxyz ($w$: prefix, $v$: suffix)
    • Reverse: $w$ = abc → $w^R$ = cba
    • Length: $w$ = abc → $\left | w \right | = 3$
    • Repeat: $w^3 = www$

Language is a subset of Σ*. However, this definition is a little bit ambiguous itself so it needs grammars.

Grammar is a language with production rules. A grammar G is defined as:

G = (V, T, S, P)
  • V variables: a finite set of objects
  • T terminal symbols: a finite set of objects
  • S start variable: NOT a set
  • P productions: a finite set of objects

A language generated by grammar G:

L(G) = {w ∈ T*: S ⇒* w}

S ⇒* $w$ can be replaced with a sentential form: S ⇒ $w_{1}$ ⇒ $w_{2}$ ⇒ … ⇒ $w_{n}$ ⇒ $w$.

Example: find a grammar generating L

\[L = {a^nb^n : n \geq 0}\] 
G = ({S, A}, {a, b}, S, P)

Production rules of P:
  S → aAb | λ
  A → aAb | λ

Automata

Automata are abstract logical machines. (singular: automaton) Every automaton accepts inputs and produces outputs. Inputs are going through the control unit (CU) to get outputs. Automata are divided by two parts as a type of behavior or output: (1) types of behavior are deterministic and non-deterministic and (2) types of output are accepter and transducer.

  • Deterministic: a move is uniquely determined
  • Non-deterministic: several moves are possible
  • Accepter: accept or reject
  • Transducer: strings produced by the control unit

There are four major automata: finite-state machines, pushdown automata, linear-bounded automata, and turing machine. First of all, let’s check finite-state machines.

DFA and NFA

Among finite-state machines, I will consider deterministic finite accepters (DFA) and non-deterministic finite accepters (NFA). Both types of automata M are defined as a quintuple in the same way like described below.

M = (Q, Σ, δ, q0, F)
  • Q internal states: a finite set
  • Σ input alphabets: a finite set
  • δ transition functions Q x Σ → Q
    • δ(q, a) = q'
    • δ*(q, λ) = q
    • δ*(q, wa) = δ(δ*(q, w), a)
  • q0 ∈ Q the initial state
  • F ⊂ Q a set of final states

There are two differences between DFA and NFA. First, DFA must have transition functions each input alphabet in every internal state and NFA do not have to. Second, NFA can have λ states between two internal states, which is not allowed for DFA.

Using this definition M, we can draw a graph. Plus, converting the graph (DFA to NFA) is possible and also vice versa. In case that you convert NFA to DFA, it is important to minimize states in DFA. If two states p and q are indistinguishable, you can combine these things as one state. If p and q satisfy the condition below, they are indistinguishable.

  • δ(p, w) $\in$ F and δ(q, w) $\in$ F
  • δ(p, w) $\notin$ F and δ(q, w) $\notin$ F

Drawing automata with JFLAP

Go to the JFLAP SOFTWARE page and download the file JFLAP7.1.jar. Execute this file with the terminal: java -jar .\JFLAP7.1.jar. Then, you can see the menu Finite Automaton at first. Click it and draw an automaton. (This program also supports to make minimal DFA!)

References

💬 Any comments and suggestions will be appreciated.

Leave a comment

You may also enjoy