Finite Automata
Theorem
The class of regular languages is closed under the union operation
In other words, if \(A_1\) and \(A_2\) are regular languages, so is \(A_1 \cup A_2\)
Proof Idea: construct a machine \(M\) simulate \(M_1\) and \(M_2\) at the same time. Remember the state that each machin would be in, by \(k_1 \time k_2\) states.
The proof should be writen Formally, which means that we should construct the quintuple by definiton
Theorem
The class of regular languages is closed under the concatenation operation.
In other words, if \(A_1\) and \(A_2\) are regular languages then so is \(A_1 \circ A_2\).
To solve the problem we meet in the proof (we don't know when zhe first piece end and the second begins), we introduce a new technique called nondeterminism
Nondeterminism¶
In a nondeterministic machine, several choices may exist for the next state at any point. Actually, nondeterminism is a generalization of determinism.
abbreviate NFA, DFA for
- The NFA is an arrow with the lable \(\epsilon\).
How does an NFA compute? Splits!
If a state with an \(\epsilon\) symbol on an exiting arrow is encountered, something similar happens. Without reading any input, the machine splits into multiple copies, one following each of the exiting \(\epsilon\)-labeled arrows and one staying at the current state.
Nondeterminism may be viewed as a kind of parallel computation or as a tree of possibilities
Warning
if reached accept state and can't move to other states, then reject.
Example
An alphabet containing only one symbol is called a unary alphabet
Formal Definition
What different is the transition function
We will show, every NFA can be converted into an equivalent DFA, and constructing NFAs is sometimes easier.
Proof Idea: Use the power set as the set of the states.
Corollary
A language is regular if and only is some nondeterministic finite automaton recongizes it
Using this equivalance, we can easily prove that the regular language close under the regular operations
Regular Expressions¶
We use the regular operation to build up expressions describing languages. The value of a regular expression is a language.
Application
Regular expressions provide a powerful method for describing such patterns.
Formal Definition
Say that \(R\) is a regular expression if \(R\) is
- \(a\) for some \(a\) in alphabet \(\Sigma\)
- \(\epsilon\), contains only the empty string
- \(\emptyset\), doesn't contain any strings
- \((R_1 \cup R_2)\), where \(R_1\) and \(R_2\) are regular expressions
- \((R_1 \circ R_2)\), where \(R_1\) and \(R_2\) are regular expressions
- \((R_1^*)\), where \(R_1\) is a regular expression
Warning
\(R\cup\epsilon\) may not equal R
\(R \circ \emptyset\) may not equal R
Equivalence with Finite Automata
A language is regular if and only if some regular expression describes it
It is easy to prove the \(\Leftarrow\) part by construction. To prove the \(\Rightarrow\) part, we describe a procedure for converting DFAs into equivalent regular expressions.
We need the generalized nondeterministic finite automaton, GNFA.
The difference between the NFA and GNFA is the transition arrows. In the GNFA, the transition arrows may have any regular expressions as labels. GNFA reads blocks of symbols from input.
Nonregular Languages¶
The Pumping Lemma
If \(A\) is a regular language, then there is a number \(p\) (the pumping length) where if \(s\) is any string in \(A\) of length at least \(p\), then \(s\) may be divided into there pieces, \(s = xyz\), satisfing the following conditions
- for each \(i \geq 0\), \(xy^iz \in A\)
- \(|y| > 0\), and
- \(|xy| \leq p\)
Example
The following languages are nonregular
- \(\{0^n1^n \mid n \geq 0\}\)
- \(\{w \mid w\text{ has equal number of 0s and 1s}\}\)
- \(\{ww\mid w \in \{0,1\}^*\}\)
- \(\{1^{n^2} \mid n\geq 0\}\)
- \(\{0^j1^j \mid i > j\}\)
The result before all can be proved by the pumping lemma, the last one need the "pumping down method".