Sipser: Section 1.3

From CSWiki

Jump to: navigation, search

[edit]

Important Points About Regular Expressions

Regular Expressions are computationally equivalent to finite automata.
One can create an equivalent NFA or DFA for any regular expression, and vice versa.

Theorem 1.54

A language is regular if and only if it can be described by a regular expression.

Lemma 1.55 &1.56

If a language is described by a regular expression, then it is regular.
If a language is regular, then it is described by a regular expression.

[edit]

Formal Definition

$R$ is a regular expression if $R$

$a$ for some $a$ in an alphabet $Σ$
$\varepsilon$ , the empty string
$\emptyset$ , the empty set
$(R 1 * )$ , the Kleene star of a regular expression
$(R_{1}\circ R_{2})$ , the concatenation of two regular expressions, usually abbreviated $R 1 R 2$
$(R_{1}\cup R_{2}$ , the union of two regular expressions

(Note: The order in which the $*, \circ, \cup$ operations has been rearranged from Sipser's definition, and now reflects the precedence of the operations.) The definition of regular expressions is recursive, with the first three items being the base cases, and the latter three being the rules of recursion.

[edit]

GNFAs

A GNFA, or generalized nondeterministic finite automaton, is a specialized type of automaton used in the proof of the equivalence of automata and regular expressions. GNFAs must meet the following special conditions:

The start state has transitions to every other state, but no incoming transitions.
There is only one accept state.
The accept state has transitions from every other state, but no outgoing transitions.
There is a transition from every state to every state, including itself, for all states except the start state and the accept state.

Definition A generalized nondeterministic finite automaton can be expressed as a 5-tuple ( $Q$ , $Σ$ , $δ$ , $q 0$ , $q k$ ), where

  $Q$    a finite set of states.
  $Σ$    is the input alphabet.
  $δ$  : ( $Q$  - {  $q k$  } )  (  $Q$  - {  $q 0$  })   $R$  is the transition function.
  $q 0$   is the start state.
  $q k$  is the the accept state.