September 22
* Example of the conceptual power of nondeterminism
Let L be a language. Define 1/2(L) to be
{x: for some y such that |x| = |y|, xy is in L}.
1/2(L) is the set of first halves of strings in L. Prove that for each
regular L, 1/2(L) is regular.
Proof: Let M be a DFA for L. M' will be an NFA constructed to accept 1/2(L).
M' uses the "finger method" as follows.
M' places the left finger on s in M, and the right finger on s_i in M
where s_i is a nondeterministic "guess" as to where input x will lead.
As aharacters of x are read, M' moves the left finger along transitions
as dictated by characters read, and simultaneously moves the right finger
along a nondeterministically chosen edge (which may be labeled with any
character, not necessarily the one of x being read).
M' accepts x iff at the end its left finger is on s_i and
its right finger is on the accept state.
Thus M' accepts x iff
* x leads to some state s_i in M, and
* there exists y |y| = |x| s.t. y leads from s_i to an accept state in M.
Formally:
Use tuple for fingers (we need a middle finger to remember
the guessed s_i state).
M' = (K', Sigma, delta', s', F'), where
K' = K_{left finger} x K{middle finger} x K{right finger} and
s in K = new start state
* delta'(s, epsilon) = {: si in S}
"Guess" the state si to which input x will lead
* delta'(, a) =
{: delta(si, a) = sl and
there exists b in Sigma s.t. delta(sk, b) = sm}
Note that the middle finger does not change after the initial guess
F' = {: si in S, sj in F}
As you can see, the left finger moved on input x to where the
middle finger guessed (si, si). The right finger moved from si
to some accepting state sj of M (si, sj).
* RE -> NFAs with epsilon-transitions
Theorem: Forall regular expressions r, construct NFA M L(M) = L(r).
Proof: By induction on the number of operations in r we show there exists an
NFA with one final state for L(r).
Base Case: Number of operations = 0. r is either
+-+ +===+
empty, so NFA is ->| | || ||
+-+ +===+
+===+
epsilon, so NFA is ->|| ||
+===+
+-+ a +===+
a in Sigma, so NFA is ->| |-->|| ||
+-+ +===+
Inductive Hypothesis: Assume property holds for r defined with <=n
operations.
Inductive Step: Prove property then holds for r = n+1 operations.
In this case there exist r1, r2 defined using <=n operations each such
that r is one of (r1r2), (r1 v r2), or (r1*).
Let M1, M2 be NFAs with one final state accepting r1 and r2 respectively
(by inductive hypothesis M1 and M2 exist). Your homework assignment will
be used to complete the inductive step.
* DFA -> RE
Theorem: Given a DFA M = (K, Sigma, delta, s1, F), construct a regular
expression r for L(M).
Proof:
Let R_{i j}^{k} = strings leading from si to sj that do not pass through
any states numbered > k (although they may begin or end at one).
Assume K = {s1, ..., sn}.
Then R_{ij}^{n} = strings leading from si to sj and
if F = {sj_1, sj_2, ..., sj_s}
then L(M) = R_{1 j1}^{n} union R_{1 j2}^{n} union ... union R_{1 js}^{n}.
L(M) = all ways to get to final states with paths that do not pass
through any states numbered higher than n.
Lemma. Forall i, j, k there exists regular expression
r_{ij}^{k} s.t. L(r_{ij}^k) = R_{ij}^k
The theorem follows from the lemma.
L(M) = R_{1 j1}^n union R_{1 j2}^n union ... union R_{1 js}^n
= L(r_{1 j1}^n) union ... union L(r_{1 js}^n)
= L(r_{1 j1}^n v r_{1 j2}^n v ... v r_{1 js}^n), which is
a regular expression for L(M)
Now we will proof the lemma.
Note that +----- +---
| R_{ij}^0 = | a: delta(s_i, a) = s_j if i neq j
| | a: delta(s_i, a) = s_j union e if i = j
| +---
| R_{ij}^k = R_{ij}^k-1 union R_{ik}^k-1(R_{kk}^k-1)*R_{kj}^k-1
+-----
How do we transition from i to j without going through states
higher than k?
Either by transitioning from i to j without going through states
higher than k-1, or
by transitioning from i to k without going through states higher
than k-1 followed by
transitioning from k to k in one move without going through states
higher than k-1 followed by
transitioning from k to j without going through states higher
than k-1.
+------------------------------------+
| |
| |<- States > k
| |
+----------------S_k-----------------+<- States = k
| ^| ^^ |
S_1----->O==========++-+| |<- States < k
| | |
| v |---> means one move
| +======O |===> means a finite sequence of moves
+------------|-----------------------+
v
S_j
We will prove the lemma by induction on k using the note.
Base Case: Let k = 0. By the first part of the note,
R_{ij}^0 <= Sigma union e and thus there exists a simple regular
expression for the finite set (the union of individual symbols and/or e)
Inductive Hypothesis: Assume forall i, j that r_{ij}^k-1 is a regular
expression for R_{ij}^k-1.
Inductive Step: Prove that there exists re for R_{ij}^k.
By the second part of the note,
R_{ij}^k = R_{ij}^k-1 union R_{ik}^k-1(R_{kk}^k-1)*R_{kj}^k-1
= L(r_{ij}^k-1) union L(r_{ik}^k-1)(L(r_{kk}^k-1))*L(r_{kj}^k-1)
= L(r_{ij}^k-1 v r_{ik}^k-1(r{kk}^k-1)*r_{kj}^k-1).
Because each of the rs are re, the entire equation is a re.
* Example
1 1
+--+ +----+
v | 0 v |
+--+----------->+====+
|s1| 0 ||s2||
+--+<-----------+====+
L(M) = L(r_{12}^2)
r_{12}^2 = r_{12}^1 v r_{12}^1(r_{22}^1)*r_{22}^1
= r_{12)^0 v r_{11}^0(r_{11}^0)*r_{12}^0
v r_{12)^0 v r_{11}^0(r_{11}^0)*r_{12}^0(r_{22}^1)*r_{22}^1
= r_{12)^0 v r_{11}^0(r_{11}^0)*r_{12}^0
v r_{12)^0 v r_{11}^0(r_{11}^0)*r_{12}^0
(r_{22}^0 + r_{21}^0(r_{11}^0)*r_{12}^0)+
We know that r_{11}^0 = r_{22}^0 = 1 v e
r_{12}^0 = r_{21}^0 = 0
= 0 v (1 v e)+0 v (0 v (1 v e)+0)[(1 v e) v 0(1 v e)*0]+
= (0 v (1 v e)+ 0)[1 v e v 0(1 v e)*0]+
= (0 v (1 v e)+ 0)[1 v e v 01*0]*
= (1 v e)*0(1 v e v 01*0)*
= 1*0(1 v 01*0)*