[15251] Formalization of Proof, Finite Automata

Formalization of Proof

First Order Logic = Prop. Logic + {$\forall$, $\exists$, $=$, “constants”, “relations”, “functions”}
Variables are now objects.
Vocabulary is a collection of constant-names, function-names, relation-names.
Interpretation

  • Specifies the universe
  • Maps constant-name to object
  • Maps relation-name to actual relation
  • Maps function-name to actual function
    Satisfiability/Tautology: Similar to that in first order logic.

Finite Automata

Alphabet: A nonempty finite set $\Sigma$ of symbols, $\Sigma = {0, 1}$ usually.
String: A finite sequence of 0 or more symbols.

  • The length-0 string is $\epsilon$
  • $\Sigma^n$ means all strings with length n.
  • $\Sigma^{*}$ means all strings over $\Sigma$

Language: A collection of strings. A subset of $\Sigma^{*}$.

Thus, we can think of a decision problem as a function:
$f: \Sigma^{*} \rightarrow {NO, YES}$
Decision problem is finding a language L such that f(element in L) is true

DFA: $L(M) = x\in \Sigma^{*}: M \text{accepts } x$.

A deterministic finite automaton is a 5-tuple:

  • $Q$ is a nonempty finite set of states
  • $\Sigma$ is an alphabet
  • $\delta: Q * \Sigma \rightarrow Q$ is the transition function
  • $q_0\in Q$ is the start state
  • $F\subset Q$ is the set of accepting states

Accept
Let $w = w_1w_2w_3…w_n$
We say that M accepts string w if there exists states $r_0r_1…r_n\in Q$ such that

  • $r_0 = q_0$
  • $\delta(r_{t-1}, w_t) = r_t$ for all $t$
  • $r_n\in F$.
    Otherwise, we say $M$ rejects $w$.
    The sequence $r_1r_2…r_n$ is called the computation trace.

Regular Languages
A language is regular if there is a DFA that decides it

Proving a language is not regular

  1. Assume for contradiction there is a DFA M which decides language L
  2. Argue there are two strings x, y which reach the same state in M.
  3. Show there is a string z such that $xz\in L$ and $yz\notin L$.
    Example: $a^nb^n$
  • $L_1\cup L_2$ is regular if $L_1$ and $L_2$ are.(Union Theorem)
  • $L_1\dot L_2$ (concatenation)
  • $L^{*}$ is regular if $L$ is.

More on Regular Languages

  1. The empty language is regular
  2. The singleton of empty string is regular
  3. The singleton of each character in the alpahbet is regular
  4. Union
  5. Concatenation
  6. Kleene star
  7. In fact, all set operations can be performed
    (On how to prove a language is regular)[http://cseweb.ucsd.edu/~clbailey/ClosureProofTemplate.htm]
    (On how to prove regular languages are closed under reverse)[http://web.cecs.pdx.edu/~hook/cs581sp11/reverse.pdf]
    Pumping Lemma Not really understand