Regularity

31 Jan 02:30 PM

Prof. Calvin

CSCI 5100

Sketch

• Review of Theorems
• Regular Expressions and NFAs
  • \(R\) → NFA
  • Generalized NFA
  • NFA → \(R\)

Review

Theorems on *FAs

\[ \forall M_{NFA}, \exists M_{DFA} : L(M_{NFA})) = L(M_{DFA})) \]

\[ \forall M_1, M_2: \exists M_3 : L(M_3) = L(M_1) \cup L(M_2) \]

\[ \forall M_1, M_2: \exists M_3 : L(M_3) = L(M_1)L(M_2) \]

\[ \forall M_1: \exists M_2 : L(M_2) = L(M_1)* \]

Regular Expressions

• Built from:
  • \(\Sigma\), the letters of the alphabet
  • \(\varnothing\), the empty set / empty language.
  • \(\Sigma^0 = \sigma\), the empty string
• Built with:
  • \(\cup\), union
  • \(\cdot\), concatenation
  • \(*\), the “star” operator

Goal:

Show that finite automata and regular expressions are equivalently expressive.

• Closure is with respect to a set and an operation.
• We note:
  • Natural numbers \(\mathbb{N}\) are closed under \(+\)
  • Natural numbers \(\mathbb{N}\) not closed under \(-\)
• We wish to apply these to languages, not numbers.

\(R\) → NFA

Atomic

• There exist atomic \(R\)
  • Built from:
  • \(\Sigma\), the letters of the alphabet
  • \(\varnothing\), the empty set / empty language.
  • \(\Sigma^0\), the empty string

Letter atomicity

• Take \(R = a : a \in \Sigma\)
  • \(M | L(M) = R\)
    • \(Q = \{q_0,q_1\}\)
    • \(\delta = \{ (q_0, a) \rightarrow \{q_1\} \}\)
    • \(F = \{q_1\}\)

Empty String Atomicty

• Take \(R = \Sigma^0\)
  • \(M | L(M) = R\)
    • \(Q = {q_0}\)
    • \(\delta = \varnothing\)
    • \(F = \{q_0\}\)

Empty Language Atomicty

• Take \(R = \varnothing\)
  • \(M | L(M) = R\)
    • \(Q = {q_0}\)
    • \(\delta = \varnothing\)
    • \(F = \varnothing\)

Atomicity Lemma

\[ \begin{aligned} \exists M_1, M_2, M_3 :\\ L(M_1) &= a \in \Sigma \\ L(M_2) &= \Sigma^0 \\ L(M_2) &= \varnothing \end{aligned} \]

Proof

\[ \begin{aligned} M_1 &= (\{q_0,q_1\}, &\Sigma, &\{ (q_0, a) \rightarrow \{q_1\} \}, &q_0, &\{q_1\}) \\ M_2 &= (\{q_0\}, &\Sigma, &\{ (q_0, a) \rightarrow \{q_1\} \}, &q_0, &\{q_1\}) \\ M_3 &= (\{q_0\}, &\Sigma, &\varnothing, &q_0, &\{q_0\}) \\ \end{aligned} \]

Composite

• ∃ composite \(R\)
  • Over other \(R\)
    • \(R_1 \cup R_2\), union
    • \(R_1R_2\)
    • \(R*\)

• Proven over NFAs
  • ∴ DFA (Theorem 2)
    • (Theorem 1)
    • (Theorem 3)
    • (Theorem 4)

Theorem 5

\[ \forall R : \exists M : R = L(M) \]

Proof

• Atomic \(R\) follows from Atomicity Lemma
• Composite \(R\) follows from Closure properties (Theorems 1-4)

Generalized NFA

Transitions

• We understand \(\delta\) as a transition relation
• In DFAs, it is a deterministic transition
• In NFAs, it is still deterministic(!), but over sets.
• However both are identity or inclusion relations
  • That is, letter \(\in\) label

Transitions that ‘think’

• Instead of identity/inclusion…
• We can use regular expressions as transition labels.

Implementation

• It is simple enough to argue for GNFAs
  • Every operation can be an NFA
  • Any NFA node can be replaced with an NFA
    • Essentially the closure options.
  • Therefore, a GNFA is equivalently expressive to NFA
• The complete proof is left as an exercise to the interested student.

Special Form

• We take GNFAs which:
  • Have a single accept state \(|F| = 1\)
  • Connections all states but \(q_0 \land q_i \in F\)
    • Unrelated states via empty language \(\varnothing\)
      • GNFA \(\varnothing\) label refers to empty language (labels are languages)
      • NFA \(\varnothing\) label refers to the empty string (labels are strings)

NFA → \(R\)

Theorem 6

\[ \forall M : \exists R : R = L(M) \]

• We will prove with GNFA \(G\).
• We will use induction.
  • Induct over cardinality of state set \(|Q|\)

Begin

• Via our simplifying assumptions of GNFAs
  • Our base GNFA has 2 states
    • A start state, and
    • An accept state.
• Define \(|G| = |Q|\) as a shorthand convenience.

Base Case

• The two state GNFA \(G\) is as follows:

Base Lemma

\[ \forall |G| = 2 := (\{q_0,q_1\},\Sigma,\delta,q_0,\{q_1\}) : \exists R : R = L(G) \]

Proof

• By definition, \(G = (\{q_0,q_1\},\Sigma,\delta,q_0,\{q_1\})\)

• By definition, \(\delta = \{ (q_0, R') \rightarrow q_1 \}\)

• Let \(R = R'\)

• \(\blacksquare\)

Induction

• We prove that GNFA of \(k>2\) states can be converted to a GNFA of \(k-1\) states.
• With our base, this suffices to prove our theorem.
  • Do we need to go over induction?

State Exclusion

• Arbitrarily select state \(q_i : q_i \neq q_0 \land q_i \notin F\)
• Take \(R_{i,j} = ((q_i, R) \rightarrow q_j)\)
  • We note going from \(q_x\) to \(q_y\) through \(q_i\) is given as \(R_{x,i}R_{i,i}*R_{i,y}\)
• Unionize with existing relation \(R_{x,y}\)
• Denote \(R'_{x,y} = R_{x,y} \cup R_{x,i}R_{i,i}*R_{i,y}\)
• Let \(\delta_{-i} = \{ (q_x, R'_{x,y}) \rightarrow q_y | q_y, q_x \in Q \}\)

Inductive Lemma

\[ \forall |G| = (k > 2) : \exists |G| = (k - 1) : L(G) = L(G') \]

Proof

• By definition, \(G = (Q,\Sigma,\delta,q_0,\{q_n\})\)

• Select arbitrary \(q_i \in Q \setminus \{q_0, q_n\}\)

• Take \(G' = (Q \setminus \{q_i\},\Sigma,\delta_{-i},q_0,\{q_n\})\)

Graphically

Omit \(q_i\)

Partition \(\delta\)

Readd \(q_i\) incident edges

Apply Union Operator

Theorem 6

\[ \forall M : \exists R : R = L(M) \]

Proof

• \(\forall |G| = 2 := (\{q_0,q_1\},\Sigma,\delta,q_0,\{q_1\}) : \exists R : R = L(G)\)
• \(\forall |G| = (k > 2) : \exists |G| = (k - 1) : L(G) = L(G')\)
• By induction, \(\forall M : \exists R : R = L(M)\)

Stretch Break

• Home