compsci(fall2008)
Wed 08/27/08
Last time
def and theorum
1.1 and 1.2 in book
grammars in 1.3 are for later
today: use these and review proofs
induction
deduction
contradiction
theorum :
Let S[1] and s[2] be two sets
then S[1] = s[2] iff s[1] n s[2]compliment) union ( s[2] n s[1]) = empty set
iff is a double implication
proof ==>
let s[1] = s[2]
show (s[1] n s[2] compliment) u (
s[1] n s[2]-comp is really the same as s[1] n s[1] compliment , since they're the same set
and we know that that is indeed the empty set by the def of compliment
similarly, s[2] n s[1]-comp = s[2] n s[2]-comp, which is empty set
so, s[1] n s[2] -comp u (s[2] n s[1]-comp) = empty u empty = empty
done with part 1.
<==
Let s[1] n s[2]-com u s[2] n s[1]-bar = empty
show s[1]= s[2]
since the union is empty, s[1] n s[2]-bar is empty and s[2] n s[1]-barr is also empty
s[1] n s[2]-bar being empty, there is no x st x in s[1] and x is in s[2]-bar
if x in x[1], not in s[2]-bar, therefore x in s[2]
by the definition of compliment
if x in s[1] then x in s[2]. therefore, s[1] subset s[2]
similarly, s[1] subset s[2], s[2] subset of s[1]. therefore, the sets are equal.
keep a list o known facts theorums and definitions!
math induction -
- - - - - - -
suppose:
1, 2, 3, 4, 5, 6,
if i can prove that 4 belongs, we have a base case,
then if k is in the hat, then k+1 is in the hat
prove something is in there
then prove that if k is in the hat, then k+1 is in the hat
since 4 is in, then 5
since 5 then 6 .. etc, etc.
example: 1 +2+3+4 ... = ((n(n+1))/2 .. prove this is true for all positive integers
proof is by induction
changing n
my base case: prove n=1
show that 1 = 1*1 +1 /2
1*2/2 = 1.
left is 1. so we're done wit the base case.
label the base case!
Induction hypothesis (IH)
for n=1 to k, 1+2+ .. +n = (n(n+1))/2
induction step - (IS)
show 1+2+ ... K+ k+1
let n= k+1
= ((k+1)(k+2))/2
write down what it is yo're trying to show
1+2+ .. +k + k+1
= (k(k+1))/2 + (k +1), by my induction hypothesis since k < K+1
= ((k+1)(k+2))/2 , my target
Theorum: a complete binary tree of height h has 2^(H+1) -1 nodes
h=0 * 2^(0+1) -1 = 1
h=1 etc
*
* *
...
proof is by induction on the height h
Base case. let h=0
Show the tree has 2^(0+1) -1 = 1 node, which is what i need to show
the complete binary tree of height 0 is a single node, so I"m done
the formula gives 1 and the tree gives 1.
so that formula gives me the number of nodes.
my IH: for a complete binary tree of height h = 0,1.. k
the tree has 2^(h+1)-1 nodes.
IS: consider a tree of height h= k+1
show it has 2^(K+2) - 1 nodes
the left subtree is a complete binary tree of height k.
and therefore has 2^(k+1) -1 nodes, by my IH
so the total number in the tree
left: 2^(K=1) -1
right: 2^(k+1) -1
root: 1
.. the some of which was the goal
recursion and induction work well together
proof by contradition
p -> q iff ~q -> ~p
so, assume the opposite ( ~q )
the goal is to now derive a false statement
theorum:
√2 is not rational
proof is by contradition
Assume √2 is rational
ie, √2 can be written as a fraction a/b, where a,b have no common devisors
√2 = a/b => 2 = a^2/b^2 -- squre both sides)
=> 2b^2 = a^2
therefore, a^2 is even
therefore, a is even
therefore a = 2K for some integer k
2b^2 = 4k^2
b^2 = 2k^2
therefore, b is even by the same argument
therefore, both a and b are even and aave a common factor of 2.
--> <--
we said they had no common factors.
we're done with 1.1.
1.2 .
alphabet ( Σ) .. a nonempty finite set of symbols
Σ = {a,b} or Σ= {0,1}
strings on Σ denote w,x,y,z
a finite sequence of symbols from Σ, possibly 0
language is a set of strings from Σ
Σ = {a,b}
L = {λ, a, ab, ba, bba}
ab and ba are two distinct strings
λ is the empty string
suppose w= a[1], a[2], a[3] .. a[n]
v = b[1], b[2], b[m]
a[i], b[j] in Σ
concatinate =
vw = all b
reverse a^r
length |w| is the number of symbols
substring = consecutive group of symbols from some place in the string
a[j] a[j+1] ...
λ is a substring of every string including λ
prefix: something that comes from frong
prefixes of w are
λ , a[1], a[1]a[2], a[1]a[2]a[3], .... a[1]a[2]..a[n]
.. take them out of the front
suffix of w = λ a[n], a[n-1]a[n] etc
properties of strings. (theorums)
|vw| = |v| + |w|
(vw)^r = w^rv^r
w^n = w concatinated with w n times
w^0 = λ
|w^n| = |w|^n
4. w^r^r = w
don't worry about order of magnitude
definitions:
Let Σ be an alphabet (for the rest of the semester)
Σ* = the set of all strings on Σ
Σ = {a,b}
Σ = {λ, a, b, aa, ab, ba, bb, aaa, aab, ... }
Σ+ = Σ* - {λ}
Def. a language L is a subset of Σ* for some alpahbet Σ
L-bar = Σ* - L
L^R - {w^r | w in L}
Let L[1] and L[2} be two languages.
L[1]L[2] = {w| w=uv u in L[1], v in L[2]}
L[1] = {a, ab, bb}
L[2] = {a, ba, ab}
{.. aba, abbab, bba, bbbab}
L* = {w | w= 0, 1, mor more concat. of strings in L}
L[0] U L U LL .. etc
so L concatinated with itself as many times as I want.
finite automata
in C++, an identifier starts with a-z or A-Z and then is any a-z or A-Z, _, or 0-9
start. at the start I haven't read anything yet
if I read a zero, 1, .. 9, underscore, etc, goto bad .. it's not an identifier
but if I start with an a-z or an A-Z, OK so far .. and it might be just one symbol long .. so if i don't see anymore, I can take it
I can continue to see letters, numbers of underscore and i'm stilll OK
if we see punctuation, we're not going to accept it.
so this is a state machine .. we have 52 transitions going from start to OK because there are 52 good possibility
but the idea is , if I process the string nike, we end up in good
7u ends up in bad
finite atamata requires me to process al the sybols
v8 -- gets us to good
coca-cola = bad (hyphen)
deerministic finite automata .. finite number of states
directed graph .. follow the arrows.. there is a particular state called start .. can be many OLK
deterministic means no matter what symbol I get as input, i know what to do
if I add randomness (non-deterministic) to this, it's not more powerful
-------
Fri 08/29/08
lab & homework will be due wed.
lab on tuesday
last time:
- proof tecniques
- sets, languages
- concatination of two Σ*, reverse of a language
strings - concatinate two strings , reverse .. etc
chppter 1 - don't care about order of magnatude, grammars
today
- 2 proofs
- deterministic finite automata (dfa)
prove the following:
given a graf G = (v,e)
the relation R defined as vRw where v,w are verticies .. where therees a simple path to w
prove that this is an equivalence relation
two vertiices are related if there's a simple path from one to the other.
simple path -- no vertex repeating. - differnet from saying "they're connected to each other"
proof:
fora ll v .. vRv?
is there a simple path from v to v .. from a vertex to itself?
yes! -- it's defined as v .. length is zero, but technically it's a simple path.
so reflexive is done.
symmetric:
show if vRw, then wRv.
vRw tells me that there's a simple path from v to w.
v = v[0] v[1] .. v[k] = w
so the path vk - v(k-1) .. etc
is a simple path from w to v because there were no repeated veritices and i'm using exactly those verticies from w to v and we know the edes are there because every edge is bidrectional
transitive:
show if vRw and wRu then vRu
if there's a simple ppath from v to to w
wRu = w = t[0], t[1] t[m] = u is a simple path
none of these verttices are repated .. might be different length
so is there a simple path from v to u
we know that combining the two paths is a paths but it's possible that sume t[i] = some v[j] .. i might have reuused the same vertex .. so we have some work to do
first vertex v[i] and last vertex t[j] such that v[i] = t[j]
v[0], v[1] v[i] -- t[j] +1 .. t[m]
.. is a simple path.
so I have transitive
usually relfexive is easy ..and either symetric or transitive have something to say.
|w| = number of symbols
w is a string
alternate definition
1) if w = λ, |w| = 0
2) if w = x in alpahbet, |w| = 1
3) if w = ua, u in Σ*, A in Σ
|w| = |u| + 1
definition = w = a, a[1], w^R
w in Σ*
if w = λ, w^r = λ
if w= x in Σ, then w^r = w.
3) w = ua, u in Σ*, a in Σ, w^r = a u^r
recoursive definitions
proove |uv| = |u| + |v|
proof is by induction on the length of v (since a is right in our definition)
base case
suppose |v| = o
therefore, v = λ
uv = uλ = u
|uv| = |u| = |u| + |v|, since |v| =0
IH
for |v| = 0,1,2, .. k, |uv| = |u| + |uv|
IS
let let |v| = k+1
v = wa, w in Σ*, a i Σ
|uv| = |uwa| = |uw| + 1
(definition part 3)
= |u| + |w| +1 by IH
finally, by def. part 3,
= |u| + |v|
last part of 1.2
deterministic finite automata (dfa)
- is an example of a state machine
- gets input, sequence of symbols or a string
- collection of states
- only real memory is the current state .. what state am I in?
idea behind state machine -- given the current description of where you are at this moment and then you get input .. you move to some other state.
like sleeping
formally -- DFA M (for machine)
Q - finite set of states -- all possible states that I can be in .. like a door -- open or closed
Σ is the input alphabet .. it must be finite and non empty to have any fun
Q[0] is an element of Q known as the start state -- all computations begin at the start state
F is a subset of Q .. set of what we call final or accepting states .. reaaly should be one to make it fun at all.
δ is a total function, meaning all domain is used - has to be if its deterministic .. called the transition function .. what teel sme , given what state im in and what input I get where should I go next. so therefore δ takes into considerateiion a state and a symbol and returns a state.
.. tell snext state.
example - M = Q[0], Q[1], Q[2], Σ = {a,b}
Q[0] is the start state
my final states are Q[0] and Q[2]
δ is
a b
q0 q1 q0
q1 q2 q1
q2 q1 q2
ida is, when finished processing a string .. if we finish in a final state we say that M accepts the string.
otherwise, we say it rejects it
all computations start at Q[0]
suppose my string is aba
q[0], on an a, goes to q[1]
so now i'm in state q[1]
the next symbol I read is a b
so i stay in q[1]
now i read the a and q[1] on a n a goes to q[2] .. q[2] is a final state, so I accept aba
we can give any input to this machine
what defines the input a bit is the Σ .. represents all allowabl inputs.
graphical representation
>((q0)) --a-> (q1) ((q2))
vertecies are thee states of M
we mark the initial state with >
- mark final states with concentric circles
edges correspond to δ such that if δ(g[i],a) then there's a edge from q[i] to q[a].
stays put -- draw a loop.
much easier than table.
accepts even number of a's and any number of b's
L(m) = all w in Σ* such that w has an even number of a's
lab -- use one memory location
what can you do with one memory loation
write a machine -- give her a graph. see attached.
Σ = {a,b}
write /give a dfa that accpets strings that being with a.
2) give a dfa that accepts strings that have at least one a
3) write a dfa that accepts only strings that
see attached paper.
must define what each state dos with a symbol
trap state: can't leave it.
2. if q0 is a final state, then lamda is in the langaage
think of what the purpose of each state is .. things become easier
3. only strings that have exactly one a.
if we do ends with an a -- we can use the reverse of the string .
-------
Wed 09/03/08
web page has correct problems now
In chapter 2.
Last time -
def section 1.2
def DFA from 2.1
Today - reivew
L*
DFA
Language accepted by a DFA
Regular language
from 2.1
L is a language, which means its a set of strings on some alphabet.
L* is all possible concatinations 0,1, or more times of strings from L
= L^0 U L U L^2 U L^3 ,...
where L^0 = λ, regardless of L
L^1 = L
L^2 = LL = uv st u in L and v in L
L^k = L^(k-1)L = { ...}
* -- star closure, Kleene star
if Σ = {a,b}
Σ* is the set of all possible strings over ab
example -- suppose L = {a, bab, ab}
L^0 = λ
L^1 = L
L^2 = {aa, abab, aab, baba, babbab, babab, aba, abbab, abab}
.. remember, a set it doesn't matter if you repeat -- it's just bad to.
if they represent thte same string, it doesn't matter the source
Let L1 = {w from {a,b} st w contains an even number of a's}
that's an infite language.
L* actually equals L1, since an even number of a's plus an even number of a's = an even number of a's
Proof.
Show that L1 subst of L1*
Since L1* = L0 U L1 etc.. clearly this holds essentially by definition.
Now show L1* subset of L1
Let w in L1*. Show w in L1.
since w in L1*, w = some u[1] u[2]u[k] st u[i] in L[1]
if w = λ, w is in L[1] since the number of a's is 0, which is even.
w is a bunch of parts .. show that w has an even number of a's
u[i] in L => number o fa's in u[i] is even
the sum of two even numbers is again even.
therefore, w has an even number of a's
therefore w in L[1]
therefore, L[1]* = L[1]
also L** = L*
2.1.
def of a DFA = (Q, Σ, δ, Q[0], F)
q = finite set of states
Σ is a finite alphabet
g0 in Q .. start state
F subset of Q -- the final states
δ : Q x Σ -> Q
toatal transition function -- definied for all pairs of suome state and some symbol
Defined a satate transition diagram - directed graph G = (V, E)
where Q = V (my states are my virticies)
edge from q[i] to q[j] iff δ(q,a) = q[j]
start states with arrow pointing at it
final states with concentric circles
Theorum 2.1 .
there exisits a path in G from q[0] to q[f] in F
labeled w = a[a] , a[2] ...a[n]
iff
M accapts W
thre's a path iff there's an accepting computation
proof in book by induction on the length of the path.
Definition
- A DFA M = (Q, Σ, .. ) accEpts a string W
iff δ&(q[0], w) = q[f] in F
the language accepted by M is L(M)
where L(M) = all w from Σ* st δ*(q[0], w) in F}
the computation .. starting at q[0] with tee first char and going to the next state .. processing the next symbol
δ* - a sequence of steps or transitions made while processing w and beginning at q[0] -- my start state
that's what δ* represents
recursive definition
δ*(q,λ) = q for all q in Q
in other words, if I don't have a symbol, i stay where I am .. can't move w/o a symbol
δ*(q, wa) where w in Σ* and a in Σ
= δ(δ*(q,w),a)
Example -
Lets's write a DFA M
st L(M) = {w in {a,b}*} st w contains the substring aab}
examples of good strings
aab, bbabaabb, aaabaa
bad:
λ, ab, abab
(substring means consecutive)
see attached
on the homework assignment .. when asked to give a DFA
write down the language
always put question .. does not have to be verbatim.
give test stringss.. to make you test your machine.
δ*, according to this definition
of (q[0], baab) = δ(δ*(q[0], baa), b)
= δ* (δ(δ*(q[0],ba),a),b)
..etc
recursive.
each δ* returns a state
.. just work from the inside out.
a way of describing the computation .. rather than saying follow the letters.
design a couple machines.
L(M) = {w in Σ* .. a string that ends with an ab
2) length of w %3 = 2
3) L(M) = some a^Mb^n where m is at least 2 and n is at least 1 .. all the a's preceed all the b's and there's a tleast 2 as and at least 1 b
4 L(M) = w in Σ* length of w ≥ 2 and the first symbol is the same as the last symbol
see attached
don't have to label the states
def a language L is a regular language iff
there exists a dfa M st
L(M) = L
a language is regular iff there's a dfa that accepts it.
every language so far hs been a regular language
regular languages are a subset of context free lang
a subset of decidable languages
a subset of recognizable languages
and everything else is unrecognizable
way more unrecognizable languages than recognizable
Theorum
If L is a regular language, then L U λ is also a regular language
Proof
Since L is regular, there exists DFA M = (Q, Σ, δ, q[0], F)
st L(M) is L by definition of regular)
if λ in L, then L U λ = L, so L U λ is regular
if λ not in L
q[0] is not a final state of M.
we need to create a DFA M-hat from M so L(M-hat) = Lu {λ}
can't just make q[0] a final state
if there are edges that lead into it if δ(q, α) = q[0] from some q in Q and α in Σ
see attach.
elminate the problms of having an edge come into q [0]
create a new state that behaves exactly the same as q[0].
-------
Fri 09/05/08
Last time:
DFA M
L(M) =
δ* = δ*(q, λ) = q
= δ*(q,w) = δ(δ*(q,w),a)
L = regular iff there exists a DFA M -> L(M) = L
show if L is regular, then L U {λ} is regular
This time:
- a few properties of regular lenguages
- introduce nondeterminism
2.1 and 2.2.
Proof - done if λ in L
so assume it's not
L = L(M) , M = (,,,,) //dfa
for all δ(q[i],a), if δ(q[i],a) is not q0, then we're done by making q0 a final state
suppose that there is an edge back into q0
then we can't make it a final state
constrct a new dfa so taht the language M-hat = L U λ
create a q0 that all the edges going oout look exactly the same .. Q-hat .. all the edes that go in go in and all the edges that usd to go out go the same way as they did before.
then you iosolate q0
idea but not proof
M - hat
q-hat = Q uion Q hat
f = f unin q0
δ-hat - f(q[i],a) = Δ (q[i], α) if
.....
and q[i] != q-hat
so for all the edges that come out of states, they all go exactly where they had before .. unless they come in.
so δ-hat of q{i], = q- hat if δ(q[i],a) = q0
δ-hat(
all the edges leading out of
δ-hat is unchanged if it din't involve q0
δ(q-hat, alfa ) = δ (q[0], α)
clearly, x in L(m-hat)
show that
that's the only thing that's in there
=> ...
if during the computatin I get back to q-hat, I have to show that there's a computation that oorks in the orignal
if in M *(q0
if we end up at q-hat .. and we process the next symbol -- .. we end up in qy, thte vey next step puts me at the same place, so the computation can continue.
if I have a sequence in δ-hat that works, then there's a sequence of δ that works
oabove
δhat (q[i], α = q-hat if δ(q[i],α) = q0
need to be able to show that for evey path in q-hat there's a path in q
....
suppose DFA M = (q, Σ, δ, q[0], F)
L(M) = L
construct a DFA so that L(M-hat) = L-bar ( = L(M)-bar)
switch the final states
M - hat = (Q, Σ, δ, q0 , Q-F) .. exactly the opposite final state.
q is final state of M-hat iff q is not final state in M.
since a dfa allows for exactly one computation per string, this works
proove that
L(M) - bar = {w in Σ* st δ* (q[0], w) in Q-F}
proof
w in L(M) iff δ*(q[0], w) in F
w not in L(M) iff δ*(q0,w) not in F
if w is not in L(M) then w is in L(M) - bar
iff δ*(q0, w) in Q-F
if M-hat = (Q, Σ, δ, q0, Q-F)
then L(M-hat) = L(M) - bar
if L is a regular language, then L U λ is regular and the compliment is regular.
Theorum - any finite language is regular
L = { aa, abaa, bbba, bab}
see atached.
but it's messy
would have been easier without connecting the other edges
.. nondetermanistic
.. what makes it so?
there are states, for example, q0 such that Δ(q0, a) is multipally defined .. we go to two different places on a
- there are states where δ(q[i],α) is not defined at all -- no edge
L = {w | w contains exactly one a or exactly one b}
= {w|w contains eaxtly on ea } U {w | w contains exactly 1 b}
exactly one a - attached.
so we have two start states .. which we can't have
with non-determinism , we can read nothing.
so the presence of δ(q, λ) makes it nondeterministic
now how do we say if a string is in our language?
example bab .
if we follow the top route, we get to a final state
if we go the bottom route .. we trap
two different outcomes!
so our definition of "accept" has to change"
if we follow the top we accept, bottom reject
2.2
L = {w|w contains "aba"}
i can do that using non-determinism easily
so seems to make our lifee asier
def. A non-deterministic finite atomata (NFA)
is a quintuple M = (Q, Σ, δ, q0 , F)
st Q is a finite set of states
Σ as before (finite alphabet)
q0 in Q, start state
F subst of Q .. final/accepting states
δ : Q x (Σ U λ)
.. so you can read nothing
-> 2^Q .. powerset of Q .. subsets of Q
.. so we don't have to go to one single state -- we can go to many different states
.. or could go nowhere -- empty set
δ(qi, α) = {q[j], q[k], q[m]} or δ(q[i], α) = empty set
δ(q[i], λ) = {q[j] .. q[k]}
δ(q[i], α) = {q[j]} <-- the singleton .. always a set.
def
q[i] in δ*(q[j], w) iff ther's a path frm q[i] to q[w] labeled w.
aλ = λa = a
. . so there could be λ in the path
if q[j] in F and q[j] in δ*(q[0], w) then w in L(M)
.. reached a final state.
M accepts w if there is a path .. there might be may paths .. of which only one of them ends in a final state.
so if therees any chance to get to an accpeting state, we accept.
finally,
NFA M = (Q, Σ, δ, q[0], F)
L(M) = strings from Σ* st δ*(q,w) interset F ≠ empty set
.. as long s one place where it ends is a final state, I accpet
Σ = {a,b}
(1) L = {w|w = uab}
(2) L = w| |w| %3 = 2}
(3) L = {a^m b^n | m ≥2, n≥1}
4 L= {w | first symbol = last symbol, |w| >w}
write NFA's ..
DFA is an NFA
see attached.
1.
δ*(q0, "aab") {q0, q2} n {q2} ≠ empty, so accept
(2) - sometimes the best NFA is a DFA
(3) for this example, we just leave off the trap state.
(4) can't separate the two whatevers
so NFA's are more flexible perhaps easier -- but be careful
questions:
implimentation
which is more powerful
next week 2.3 2.4, 3.?
-------
Mon 09/08/08
equivalence relation
reflexive - xRX
symmetic - xRy -> y R z
transitive
xRy yRz -> xRz
for example:
R ≤ integers
xRy iff x≤y
reflexive? yes 3 ≤3
symmetric
if x≤ y => y ≤ x ? no!
.. fails
transitive? yes
uRv if they have a common symbol
"cat" is not related to "dog"
cat R camel
transitive! come up with a counter example
no!
4.
1 and 2
get to use definition of length
2. recursive definition for reversal
Last time:
- introduced non-determinism
NFA m = Q Σ, δ, q0 , F
δ : Q x (Σ .. ) number of states 2^Q
today
motivation for non-determinism
dfa vs nfa .. wo's more powerful
- equivalent
NFA -> DFA
non-determinism should not freak us out .. because:
you've done all kinds of things that ere not determiinistic
all the things with recursion -- take a fork, try to solve it -- if it didn't work , backtrack
so you have choices
and it it doesn't work , you back track
gives us choices ..
when do we backtrack
- if we process a string and get stuck (no transitions)
.. backtrack for current symbol
.. if we reject then we backup
- but if we get to the accept state, we accept and quit
a couple nfas
Σ = {a,b}
1) every odd position is an a
2) every aa followed by b
3 exactly two a's
4 even number of a's
5 contains aa or ab
#1 = one of her favoirtes!!
#2 - non determinism doesn't always buy us all that much
#4 allows us to do concatination
#5 union of two languags
suppose l1 and l2 are regular .. oncstruct an nfa that accepts l1 and l2
= M1 st L(m1) = m1
m2 st l(m2) = m2
connect the two start states with lamda
can't do that with dfa's
but if this is an nfa and the other is an nfa, then the whole thing is still an nfa
so they nfa allow us to combine machines in simple ways.
for today:
theorum: Let L be a language over Σ
then there exists a dfa M[d] = qd, Σd, q0d, fd)
st L(M[d]) = L
iff there exists nfa M[n] = (Q[n], Σn, delta n, q0n, f,d)
st L(m[n]) = L
if I have a nfa, I have a dfa
corralary
L is a regular language iff there exists nfa M st L(M) = L
definition - two finite atamata whether they be deterministic or not are equivalent iff they accept exactly the same language
have to be able to convert an nfa to a dfa
have to get rid of multiple edges, get rid of edges that wrre not defined get rid of lamda
example -- see attached.
δ = δ*(q,w)
δ* = there's a walk path from q[i] to q[j] labeled w
δ*(q0,a) = where can I get on an a starting at q0
I can read an a and get q1
but q2 is also in there because aλ is a
δ*(q0, bb) = {q1, q2}, becaase of λ
δ*(q0, b) = q1 and q2
δ*(q0, aa) = {q0, q2} -> ha! can't follow λ
δ*(q1, aa) = {q1, q2} λ again!
δ*(q0, ab) = δ*(q1, b) u δ*(q2, b)
= {q1, q2} U {q1q2} = {q1, q2}
have to model both computations at one time
proof.
=>
let M{d] be a DFA = (qd, Σ, δd, q0d, fd)
L(M[d]) = L
we can construct nfa
M[n] = (qn, Σ, δn, q0n, dn}
Qn = {{q[i] | q[i] in qd}
δn( {qi}, α) {δd(q[i],α)}
q0n = {q0d}
Fn = {{qi}|qi in FD}
changed q[i] in d to the set of qi
easy to convert a dfa to an nfa .. it is one -- the results of all my computations are singleton sets
timeout for an example
here's an nfa to convert to dfa .. see example attached.
NFA start state is q0 .. dfa {q0} is my start state
the states in the dfa willl be subsets of states in the nfa
the dfa has to model the computations that are occuring in the nfa .. the nfa mihgt have multiple tracks
see attached .
every possible combinatin is possible -- we could have 8 states.
δ*({q1,q2,q3},a) = ?
δ*(q0,a) U δ(q1,a) u δ (q2,a)
so in this example, we're looping -- once we have them all, don't have to compute the last two.
δd({q0,q1,q2),b)
δn(q1,b) u δn(q1,b) δn(q2,b)
= empty u empty u {q1 q2}
= {q1, q2}
so that's a new state in the dfa.
everytime we add a new vertex, have to figure out the two edges
this algorithm will terrinate because there's a max a 8 states
δd({q1,q2},a) =
{q0, q1} u {q0q1}
so we need a q0 q1
q0q1 on an a
there are three other possible sttes, but we can't reach them .. so we don't need them.
final states -- anybody who has a final state in the nfa.
.. those verticies with any state a final state in the nfa
is λ in the language?
.. not this one
need to formalize this .. but that's the idea
idea = parallel computation -- doing all possible paths at once .. which is huge
exam question -- give partial and ask to compete it.
proof <=
proof is by construction
ie, from the nfa, create a dfa
procedure
1 - create the starte state of the dfa as {q0} where q0 is start state of the nfa
2. repeat until no missing edges
- choose a state q[i], q[j] .. q[k] of the dfa that i'm constructing that is not yet defined for some α from Σ .. it's got a missing edge
- compute δn* (q[i],α) u δn* (q[k],α) u ... u δn* (q[k],α) u
δ* - because we can follow λs
= {q[r], q[s], q[t]}
3. if there's no state labeled {q[r], q[s] .. q[t]}, add it
4. add edge labeled α from state {q[i], q[j], .. q[k]} to {q[r], q[s] .. q[t]} .. so add the edge we justried to figure out.
end repeat.
if the state {qa,qb .. qc} in my dfa contains a final state from the nfa then {q[a], qb .. q[c]} is a final state in the dfa, so mark it
finally, if λ is in the language of the nfa, then the state q[0] of dfa is also final.
another example:
attached.
-------
Wed 09/10/08
Last time:
- 2.3 = NFA -> DFA
to show that a language is regular, an nfa or a dfa will do
Today: complete the proof
advantages of an nfa / kinds of things we can do in proofs
skip 2.4
start chapter 3.
def. - two finite automata M1, and M2 are equivalent if they accept the same language
L(m1) = L(M2)
Theorum:
1) Let M = (Q, Σ,δ, q0, F) be a dFA,
then there exists an NFA Mn = (q[n], Σ, δ[n], q0n, Fn)
such that L(M) = L(M[n])
let m = (Q, Σ,δ, q0, F) be a NFA, then there exists an NFA Md = (q[d], Σ, δ[d], q0d, F[d])
such that L(M) = L(M[d])
doesn't mean exactly one -- just shows us how to get one, not that it's the only one.
Proof of 1)
NFA , DFA
Let Q[n] = Q
q[0][n] ] q[0]
F[n] = F
δ[n] : Q x (Σ u {λ}) -> 2^Q
δ[n](q[i], α) = {q[i]|δ(q[i], α) = q}
Show L(M) = L(M[n])
w in L(M) iff qo,q1,q2 .. qn is the accpeting computatin in M
as well as in M[n] by def in δ[n]
.. the same computation works in both of them.
Proof of (2)
Proof byy construction
algorithm from last time
highlights:
DFA M[d] = (qd, σ, δd
where q0d = {q0}
my states in my dfa represent substates in the nfa
2. δ([q0,q1,q2 .. qn}, α) = δ*n(qi) U δ*n(q2) ...
so where can I be in the nfa (use of δ* allows us to follow λ's)
3. final states
{qr, qs, qt} n F ≠ empty ==> {qr,qs,qt} in Fd
.. if there's a final state in there, I would accept that.
4. if λ in M then {q0} = Fd
show that the language accepted by this dfa is the same as the language accpeted by the nfa
does our algorithm terminate? might produce |2^Q| which is the same as 2^|q|, which is finite because the nfa has a finaite number of states
each of which has |Σ| edges
number of iterations is ≤ 2^Q * |Σ|
.. so it can be large, but it does terminate
NOw show w in L(M) iff w in L(M[d])
w in L(M) iff δ*(q[0], w) in F ≠ empty
iff there exists a path in the transition graph / accepting computatin q0qi1qi2 .. q[ik] in F labeled w.
iff ( via def of δ[d])
w = a1.. a2 .. an // not k .. could be different
q[i] in δ[d] ({q0}, q[1])
for q[i] in δ*(q0, a)
if I"m q0 and I read a1, I'm at some state q1 .. qi is a member of that state .. but only if when I processed from q0 in nfa, I ended up with q[i]
δ*({q0}, w) = δ(δ*( ...)
but the idea is .. i can build the accpeting computation
δ*({q0}, w) = { ~~~~~ qik ~~~ | in F[D} since q[ik] in F (ie, in nfa)
One more example:
attahced.
convert it just cuz
L(M[d]) = w | w does not end wwth two or more a's
nfa --> dfa does not guarentee me the smallest dfa
smaller is nicer.
our alg. does not guarentee the smallest.
2.4 is about taking a dfa and making it the smaalest dfa that accepts the same language
eventually nfa --> dfa --> minimal dfa
why bother with nfas?
(we know they're equivalent)
a langaage L is regular iff there exists a dfa M such that (M) = L
theorum -- a language L is regular iff there extist NFA M st L(M) = L
nice to have both
the freedom of lamda transitins and multiple s .. allows us to do alot with nfas
proffs
(==>)
suppose L is regular
by definition, there exits DFA st L(M) = L
by our last theorum,
for every dfa there is an equivalent nfa
so there exits nfa M[n] where L(Mn]) = L(Mn) = L(M)
so for every regular language there is an nfa that accepts it
(<==) = we have an nfa M where L(M) = L
by our theorum, we have a dfa st L(Md) = L(M)
by definition , since we have DFA M[d] whee L(M(d) = L, that means, L is regular.
NFA ==> DFA ==> regular
now to prove something regular you can give either an nfa or a dfa
proove a couple things.
Theorum
1) Let L be a finite language, then L is regular
(2) Let L be a regular language. Then L^R = {w| w^R in L} = {w^R|w in L}
is also regular
L is a finite langaage meas that L is some fixed number of strings. .. L = {w0, w1 .. wn} w[i]= Σ*
do it with an nfa
proof is by induction on the size of L .. ie, |L|
Base case |L| = 0
(q0) ((q1)) .. no edges .. this NFA accepts nothing
|L| = 1 where w = a1a2a3 ..an
Constrct NFA M
(q0) -- a1 --> (q1) .. ((qn))
Q = {q0 .. qn+1}
F = {q[n]}
δ(qi, a[i+1]) = q[i+1} for i == 0,1,2 n-1
L(M) = {w} {w} is regular
IH for |L| ... K == is reegular
IS Let |l| = k+1
L = {w1 .. wk} U {wk+1}
L[k] {w1 .. wk} is regular by my induction hypothesis
L[1] {w[k+1]} is regular by base case
nice L[k] .. there exists a DFA .. ( .. where L(Mk) = Lk
L1 regular says exits a DFA .. where L(M1) = L
q1 n qk is empty
construct nfa M (Q, Σ, δ, q0, F)
Q = q1 u qk u Q nu
F = F1 u Fk
δ(qi, α) = { δ[1](qi, α) q in q1
δk(qi, α) q in qK
{q0, q0k} q = q0, α = λ
show that w in L[k+1} iff w in L(M)
w in Lk ,, then q0 .. q0k .. in Qk
if w in L1 .. q0 q01 .. qf in Q1
so this is partly why nfa is so nice
no tight restriction of DFA
If L is some regular lnaguage and I want to accept the reverse of it ...
.. just reverse every guy in there there .. .. rversee edges ..
Q0 = F
QF = start
if we have multiple final states .. introduce a q-hat and lambda
so nfa's buy me easier ways to do things.
-------
Fri 09/12/08
Last time:
for every nfa, there is a dfa
finite languages are regular
if L is regular, then L^R is regular
2.4 for monday & tuesday - dfa to minimal dfa
Theorum:
L is regular => L^R is regular
L^R = w| w^R in L
Proof
L is regular => there exists dfa M = (Q[d], Σ, Q[d], Q0[d], F[d])
where l(M) = L
construct an NFA from M NFA = M[n] = Q[n], Σ, δn, q0n, Fn)
general idea -- if I have some start state and I ned up in some final state, I really want to just reverse the edges, make a new start state and send it into the final state with λ's
has to be nfa becuase of λ and its possible that I had a statewhere reversing thee edges causes multiple definition
construct as folows
Q[n] = q[n] U {qon}, a new state
F[n] = {q0d}
Σ .. same languages
δn q[i] in δ(qj, α) iff δd(qi, α) = q[i]
δn(q0n, λ) = {q| q in F[D]}
L(M[n]) = L^R
w = a1a2..an
w^r = an an-1 .. a[2] a[1]
in dfa = there is aa sequence q q2 .. qin .. is a sequence of states in an accpeting computation off w^r.
now show that w is in L(M)we kno the reverse is in the DFA
by my deffinition of δn, I know that δ[n](q0n,λ) includes a λ transition
by q[i]n in Fd, qn in δN
DFA q0d == a[n] --> O -- a[n]-1] ..
because it is a dfa, there are no λ transitions .. no place oo q
NFA .. qon --> qin --> qi[n-1] , by definiition of δ and the idea that there's one accepting computation in a dfa.
so we shoudd really induct on the lenght of w .. but we don't care
we know that all the flips exst becuase that's how we defined it .. did have to talk about how to get foom q0 to one of the final states in the DFA
δ[n] l.. we flipped everything.
Show L = {w|w ends wwth ab| is regular
L^R = {u | u begins with ba}
.. that's an easy machine
L^R is regular therefore L is regular
becaase the reverse of a language is regular
suppose L = {w|w contains subsequence aa}
.. the reverse of the language is the same as the language .. lets do..
suppose L = {w|w contains subsequence ab}
construction of L^R
NFA that does accept anything with the string ba
how to apply that stuff:
chapter 3:
regular grammars regular expressions, : regular languages
two more ways of saying something is regular
Def: Let Σ = {a,b}
1. empty set, λ, a, and b are primitive regular expressions (λ is the empty string , empty set is no strings at all)
2. if r[1] and r[2] are regular expressions, then r[1].r[2] is a regular expressions
(r[1]) is a regular expressions
r[1]* is a regular expression
r[1]+r[2] is a regular expression
so i have four ways of making a regex out of one that arleayd exissts
3. a regular expression s constructed from thh prmitives using a finite number of constructions from 2.
examples:
a - is a regular expression
a+b
a*+b*
(ab)* //leave the . out if you like
((empty +a*)+ab)*
all valid!
things not OK
Σ*
Σ* - a*b* // we don't get -
we don't get ?'s for one or many
don't get to use compement, not minus
we use regular expressions to describe languages
Def. the language L definined by a regular expression:
(1) L(empty) = empty
L(λ) = {λ}
L(a) = {a}
L(b) = {b}
(2) L(r[1].r[2]) = L(r[1])(dot) L(r[2]) // concatinated
L((r[1])) = L(r[1])
L(r[1]+r[2]) = L(r1) U L(r2) .. w in L(r1) or w in L(r2)
L(r1*) = {L(r1)}*
closure {w| u1 u2 u3 .. un ..
i can pick strings ut of the language and onatinate as much as I want
Let's write a regexp that gives me the language blah.
L = { a^n | N = 1,2,3 .. } ..
so λ a, aa, aaa, aaaa, ..
need a regexp that gives that.
a* .. regular expression
L(a*) = (L(a))*
.. so we get to concat a many times
call the new language L[1] .. don't have to prove languages
suppose my regexp =
ba*b
L = w| w = b a^n b, n=0, 1 ..
b+a*
L(b+a*) = L(b) U L(a*)
= b U a^n where n=0,1,2 ..
so either b or all a's
regular expression: a+b
L(a+b) = {a,b}
(a+b)*
= (L(a+b))*
.. that's Σ* .. everything
not the only regexp that represents Σ*
a*b* .. any number of a's concatinate with any number of b's
L((a*b*)*) is also Σ*
no esacpe characters, no 0,1,or more
regexp = λ+a
L(λ+a) = L(λ) u L(a)
= {λ, a}
b(λ+a)
L(b(λ+a) ) = L(b)L(λ+a) = {b, ba}
complement is a little harder
Σ = {a,b}
L[1] = w| |w| = 3}
l2 = w|w |w| ≤ 3
L3 = w|w has exactly 1 a
l4 = w|w has at most one a
l5 = w has at least 1 a
l1 = (a+b)(a+b)(a+b) or aaa+aab+abb .. bbb
l2 = λ + (a+b) + (a+b)(a+b) + (a+b)(a+b)(a+b)
or (λ+a+b)(λ+a+b)(λ+a+b)
huge difference between regexmp and dfa .. dfa has exactly one accpeting computation
l3 = b*ab*
l4 = b*(λ+a)b*
l5 = (b*ab*)(b*ab*)*
or (a+b)*a(a+b)
l6 = {w| |w| is odd}
L7 = {w | w contains aba}
L8 = {w| w does not contain aa}
L9 = {w | w ends with ab}
L10 = { w does not begin with aa}
L9 = (a+b)*ab
contains aba
(a+b)*aba(a+b)*
L6 = (a+b)((a+b)(a+b))*
does no begin with aa
λ+b+a+(bb+ba+ab)(a+b)*
w does not contain aa
λ+a+b+((λ+a)bb*)* .. misses things ending in a
λ+a+b+((λ+a)bb*)*(λ+a)
regular expression denotes regular languages
regular expression -> nfa
every regexp specifies a regular language
for every dfa, there's a regexp
for every language i have a regular expression
easy to turn a regexp to an nfa .. but can have a huge number of states
-------
Mon 09/15/08
3.
b[1] = {a, aa, aaa, ..}
b2 = {aa, aaaa, aaaaaa, ..}
b3 = {aaa, aaaaaa .. }
show b1 is regular .. draw the state diagram
b2 is regular 0--> 0 --> 0 which loops back to q0
given a machine for bk, can I construct a machine for bk+1
solve inductively on k
last time:
regular expressons
defined and
L(λ) = {λ}
L(empty) = emtpy
l(a) = {a}
L(r[1]r[2]) = L(r1L(r2)
a couple regular expressions
Σ = {a,b}
L{1] = {w|w contains an odd number of a's}
L2 = w | w begins with ab or ends with ba}
l3 = {a^nb^m where n+m is odd}
l1 = b*ab* (b*ab*ab*)*
exactly 1 a and even number of a's
L2
ab(a+b)* + (a+b)*ba
(a+b)* = Σ*
no!! --> (λ+ab)(a+b)*(λ+ba)
L3 =
n odd, m even
m odd, n even
a(aa)*(bb)* + (aa)*b(bb)*
(aa)*(a+b)(bb)* .. also works
write nfa for l3
comes directly from the regexp
can take any regexp and produce an nfa
section 3.2
theorum
Let r be a reg expressoins and L = L(r)
Then L is a regular languages.
Proof:
r regular expression = > construct an NFA acccodring to some rules
L = L(M), so L is regular.
reg exp -> NFA -> DFA -> regular language
REgular exp |L | NFA
-----------------
λ |{λ} | >((qo))
empty | empty | >(q0)
a in Σ | {a} | >(q0) - a -> ((q1))
r[1] + r[2] | L(r1) + L(r2) | see attached.
(r1) | L(r1) | same
see attached again for * closure
If I have a regular langauge, I Have a regexp .. a lot harder
(a+b)(aab)*(λ+a) . we could produce an nfa for that hopefully in a few seconds -- attached.
could do it smaller but nice to have something mechanical .. JFLAP
2.4 .
DFA --> minimal DFA
def. DFA M = (QΣ, δ, qo.. F) is a minimal DFA for L(M) if for every DFA M' = (Q', Σ, δ, q0, F') st L(M') = L(M)
|q'| > |q|
.. I have the smallest number of states possible
def. given a DFA M = (Q, Σ, δ, Q0, F)
two states p and q are indistinguishable (they do exactly the same thing) if for all w in Σ* .. for every single string δ*(p,w) in F iff δ*(q,w) in F
start and p or q , pprocess w
if i start at p and accept w, then q has to accept w, if i reject, then i reject in q
hard to prove .. so we usually try to prove the opposite
if exists some string w in Σ* for which
δ*(p,w) is final and δ*(q,w) is not final or other way around.
then p and q are distinguishable .. they behave differently
this is DFA .. that's absolutely essential here.
silly little DFA example:
attached.
claim - q0 and q1 are distinguishable
a works in this case .. q0 on an q goes to q1, a final, q1 on an a goes to q2, which is not final
λ also works
if qi in final and qj not in final, then qi and qj are distinguishable with w = λ
q1 and q2 are distinguishable
can I merge q0 and q2?
on a go to the same, on b they go to the same,
.. so the two states are indistingusihable
so we can make a 2 state machine .. we know that's minimal becaase final and not final are distinguishable.
next example attached:
algorithm for determining sets if indistinguishable states
1. remove all inaccessible states (DFS, BfS from start state)
2. consider all pairs of states (p,q)
if p is final and q is not, mark as distinguishable
if q is final and p is not, mark as distinguishable
3. Repeat until no previously unmarked pair is marked as distinguishable for all (p,q) not yet marked
compute δ(p,a) = p[a] and δ(q,a) = q[a]
if (p[a],q[a]) has been marked as distinguishable, then mark p and q as distinguishable
(0,1) (0,2) (0,3) (0,4) (0,5)
//don't need to list (1,0).
(1,2) (1,3)
... all possible pairs
and a state is never istinguishable from itself
do step 2.
(q0, a) = q1
(q2, a) = q5
we don't know anyting about 1,5 so we can't do anything there but check b
(q0, b) = q3
(q2, b) = q2
(2,3) has been marked, therefore, I can mark (0,2)
now look at (0,4)
0,a
4, a
go to 1 and 5, which we don't know about
b's
q0, b = 3
4
3,4 has been marked, so I mark 0,4
(1,3)
q1,a = 2
q3, a = 4
don't know
q1, b = q3
q3, b = q1
so can't do anything about 1,3 yet
(1,5)
goes to 2,5 on an a, .. so we can cross out (1,5)
(2,4)
a .. both go to q5
b .. 2 to 2 and 4 to 4
so unlikely that i'll ever distingish
(3,5)
q3, a = q4
q5, a,= q5
so we can cross (3,5)
we've gone through the list once, but we've made some changes so we go through again.
so the next pass through, no changes.
so 1 and 3 are really the same state
2 and 4 are really the same state.
so smaller, four state dfa.
now all states are distinguishable .. so we can't make it smaller.
-------
Wed 09/17/08
lab1
tile problem to (r,s)
.. when will I get to (r,s) precisely
problem 4 ..
S is a set of elements, 2^S is the powerset of S
Base case:
was correct.
IH. For |s| 0,1,2, .. k |2^S| = 2^|K|
IS. Let |S| = k+1
|S[k]|k = k
the size of the powerset S[k] = 2^K
observation .. every subset of S[K] is also a subset of S
let t be a subset of s[k]
t U a is a subset of s
this gives another 2^k subsets of s
|2^s| = |^sk|+2^K
= ... 2^(K+1)
= 2^|S|
Logic:
------
if (p->q) then ~q->~p
contrapositive
given A n b is empty and C subset B, show a n c is empty
.. on paper in red ink
exam1 here: friday 26th in class .. chapters 1-3
languages exam: monday sept 29th
old exams posted on web site
no entire conversion from NFA to DFA
last time:
dfa --> minimal dfa
- indistinguishable states δ*(p,w) is final iff δ*(q,w) is final for all w in Σ* .. in other words, starting foom the two states, i'm either always in a final state or i'm not .. so they agree on each and every string
that's hard
alg for indigstinguishable states
(1) mark as disgtinguishable all (final , non final) pairs .. we're using the string λ here .. these two states differ based on λ
the first iteration through all remaining pairs
w = "a" or w="b" .. now i'm going to look at the a or I look at the b
and if that distinguishes them,
next iteration ..
looking at strings of lenghh 2
and the bigg deal is etc .. every tme i go through the list i'm lengthening it out
and we could keep track of the string
deal with half the array
chapter 3 .. regular expressions and regular grammars
regExP --> NFA <==> DFA <==> regular language
Create an NFA for L(aa* + (a+λ)b*a)
according to tconstruction theorum
all on page 78 and 79
see attached.
another theorum
let L be a regular language.
Then there exists a regular expression r , L=L(r);
proof is by construction
DFA --> REGEXP
pages 80-85.
start section 3.3
Regular grammars
section 1.2
Def: a grammar G = (V, T, S,P) where
V is a finite set of variables (non-terminals)
T is an alphabet (finite) .. the terminals
S in V is our start symbol
P is a finite set of production rules x ==> y
where x in V union T+
y in V union T*
left is a mixture of variables and terminals
and right is a mixture .. possibly empty
S ==> ab, aa
aA ==> baa
B ==> B | λ
terminals are lowercase, variables are uppercase
take a left side and replace it with a right side
sentential forms
we're not crazy about such wild grammars as that
strict rules
definition: a grammar G = (V, T, S, P) is a right linear grammar if all rules are of the forms
A-> xB or A --> x
where A , B in V, and x in T*
one lousy variable on the right at most AND at the end
a agrammar is left linear
if it is of the forms
A --> Bx or A --> x, AB variables x in T*
definition part 3 - a grammar is a regular grammar if it is either right linear or left linear
S ---> aA|bB
A --> aA | bB | λ
B -> bB | λ
right linear and therefore regular
S --> Aa | Bb
A --> Aa | λ
B --> Bb | Aa | λ
that's left linear and therefore regular
S --> Aa | Bb
A --> aA |λ
B --> Bb | λ | Aa
is NEITHER although it manages to generate exactly the same language
S --> aSb // kills it right here
also NEITHER
yet they all generate the same language
right does it from front forward
left does it from rear forward
w| w has exactly 1 a
T = Σ = {a,b}
I want a regular grammar
some number of bb's , a a and then b's
S--> bB | A
B -> bB | A
A -> a | aC
C -> bC | λ
---
begins with an ab
S --> abA
A --> aA | bA | λ
l3 = w| w ends with bb
S --> Bbb
B --> Ba | Bb| λ
a regular language is going to have a regular languages v ice versal
-------
Fri 09/19/08
Exam I
chapters 1-3 and we've kinda covered 4.1
background material -- sets, induction, string
covers dfa, nfa, regexp, regular grammar
algorithms involved
everything about regular languages except how to show something is not regular.
Last time:
regular grammar
either right linear .. all the rules look like A -> Bx or A->X where x is some number of terminals and A, B ar evairables
left linear .. A--> xB, A-X, where ex in terminals a, b variables
Today:
L is regular iff there exisits a regular grammar G such taht L(G) = L
define:
Let G = (G, T, s,P) be a grammar
(w in T* | --> W}
where zero one or many derivation steps as given by P
T is really my Σ .. my terminals
L[1] = {w | w contains exactly 2 a's
l2 = {W contains two or less a's}
L3 = {w| w begins and end with same symbol|
L4 = {w = | every even position is a b}
L5 = {w does not end in bb}
L6 = { w|w doe snot contain b}
Not regular:
s --> BaBaB
B --> aB | A
works but is not a regular grammar .. doesn't mean that the language isn't regular .. just that the grammar isn't
a regular grammar for L1
G1
S -> bB |A
A[1] -> aB[1]
B[1] --> aB[2]
B[2] -> b B[2] | λ
B --> bB| A[1]
use subscripts in this case to say how many a's we have
suppose I have 0,1, or 2 a's
so we can change this so taat any of the b's prooooooooooooooooooooduuuuuuce nothiiiiiiiiiiiiiiiiiig
L5
G5
S -> Aaa|Aab|Aba|B
B -> λ|a|b
A -> Aa|Ab|λ
G6 any time I see a b, I must quit or generate an a
S -> bB |bA |λ
B -> aA |λ
A -> aA| bB | λ
so far anyting we put on the board
should be able to write a regular grammar
reg exp
NFA
DFA
why regular grammars give me regular languages
easy direction first
Let L be a regular language
then there exists right linear grammar G = (V, t, s, p) st L(G) = L
proof is by construction of G
L is regular
therefore there exists DFA M = (Q, Σ, δ, Q0 , F) st the L(M) = L
I have a dfa that accepts L
a DFA has exactly one path through it
we can create a DFA for starts and ends with same symbol
going to use a grammar that has the same states
my variables are {q0, q1, q2, q3, q4}
my terminals are a and b
S = q0
q0 => aq1 | bq3
q1 -> bq1 | aq2
q2 => aq2 | bq1 |λ - final state
q3 -> qa3 | bq4
q4 -> aq3 | bq4 |λ - final state
edges in the the DFA tell me exactly what rule to use down in the grammar
now we have to generalize that
pretty easy .. just remember the final states
for G = (V, T, S, P)
V = Q (variables = states)
S = q0 - start symbol is my initial state
T = Σ .. my terminals are my alphabet
P + {qi -> αqj where δ(qi,α) = qj|
U
{qi -> λ | qi in F}
now show L(G) = L(M)
all comes down to correspondance between sequence and rules followed
Let w in L(M)
δ*(q0,w) in F
therefore, q0, qi1, qi2, .. qin is an accepting computation of w = a1 a2 ... an
this means taht
δ(qij, a[j+1]) = Q[i][j+1].
iff q[i][j] -->> qi qj+1 in P
by definition I have that rule in P
q[0] ==> wq[i][n]
But qin in F, so qin -> λ in G
so q0 dervies w in G
terefore w in L(G)
L(M) subset L(G)
Show that L(G) subst L(M)
.. go backwards
it all comes down to the definitinn of P
Let G be a right linear grammar
Then L(G) is regular
Proof is by construction of NFA M st L(M) = L(G)
suppose
S -> aaA | bbB
A --> aA | bA | aa
B -> bB | aB| bb
nfa attached.
now the problem is in describing it
when i generate these new nameless states, it s one-time use
but they have to be unique
introduce a single final state
states are variables, vf, and nameless
rules for these cgusy come from moving along the path
M = (Q, Σ, δ, q0, F)
F = {Vf}
Q = V U {V[f]} U {nameless states}
q0 = S
Σ = T
define δ and tht's awkward because ff this idea of anmeless states
for each rule V[i] → VkVj
Vk = Vk1 Vk2 .. Vkm .. some number of symbols
Vi , Vj are variables
δ(vi, vk1) = Vi1 (names less state)
δ(Vi1, Vk2) = Vi2
for each rule
Vi → α1 α2 .. αm
V1 -- α1 --> 0 ---α2 -> .. V
show L()M = L(g)
w in L(G)
w is some colleciion of symbols V[1]V[2] ... V[k]
V0 -> v[1] V[1]
V1 → ...
so we eventually get there
can get from a right linear grammar to DFA
what if we have a left linear grammar
ex: does not end in bb
suppose I want the NFA that goes with that
our author deos something really neaky
for every role
A → bB replace A→b^R B
...
we get does not start with bb
.. L ^R
create the NFA M and then from that guy , we can create the NFA M-hat st L(M-hat) = L
you can get a grammar for L^R simply by revering the rules .. only works for regular languages
palandrome .. not regular language
-------
Mon 09/22/08
Exam friday!
chapters 1,2,3 and 4.1
mathematical background - strings, induction, concat of strings and languages, closure of language .etc
regular languages
- dfa
- nfa
- reg exp and regular grammars
constructions
- NFA <=> DFA
DFA => regular grammar
regexp to an nfa
regular grammar to nfa
nfa to reg exp today
NFA --> DFA construction
al
lab output should tell who are distinguishable
last time:
----------
I can take a regular grammar that is right linear into a DFA
and I can take a DFA into a riight linear grammar
trick:: don't forget the final states!
q0 = _> aq2 | bq1
q1 → aq2 | bq3
..
trap state .. can kill them but be consistant
and put the λs at final states.
grammar to NFA
A --> α1α2 .. αk B αi in sigma
then introduce the rule .. with one time use states
similarly for β1β2 ..
introduce more states for the b
and a final state .. have to introduce that
one final state.
A -> B .. that's a λ transition
everything was about right linear sop we have
Theorum:
a language L is regular iff there is a regular grammar G st L(G) = L
(=>) L is regular . I have a DFA M L(M) = L .. convert to G which is right linear where L(G) = L .. we know that ocversion that was the other guy
to go the other way, G is a regular grammar -- get to asssme that .. but there's two kinds of regular grammars
if G is right linear , we convert to NFA and we're done
because there's an nfa tells me that my language is regular
but if G is left-linear, we don't know how to do that.
this is that thing from last time
if G is left linear do the following
1) Construct g-hat
where if A -> Bx in G then A -> x^R B in G-hat
so we reverse the rules
if A -> x in G
then A -> x^R in G-hat
L(G-hat) = L(G^R)
convert G-hat into nfa Mhat
finally, three convert M-hat to M by reversing all edges , adding one new initial state δ(qnew
λ goes to all finales in m-hat
L(M) = L(G)
therefore, L is regular
so it's a huge lengthy construction .. but we don't have to do it
so now we can assume whatever we want when it is time to show something is regular
so on the homework for this week,
there's a problem:
L is regular
L[1] = {uaa | u in L|
Show L[1] is regular
L is regular.
Let M be the dfa
or Let r be the regular expression st L(r) is L.
or let G be a regular grammar st L(G) is L
choose the regular expression.
raa gives me L[1]
L(raa) = L(r)(aa)
= L * {aa}
Let L[1], L[2] be regular languages
Let L = {uv | u in l1 , v in l2}
show L is regular
DFA
glue the M's together with λ
and that was hard
use reg exp
L1(r1) L2(r2)
...
so the concatination of regular languages is regular
how would I do with the grammar
L(g1) = L1
l(g2) = l2
g1, g2 right linear
G1 = some (V1, s1, t, p) g2 = ...
and v1 n v2 is empty .. how hard is that .. rename them .. so they don't use the same variables
so then G =
V[1] u v[2], s[1], T, P[1]^ U p{2] union a few mooe .. because i need to start from s1 to porcess use and I need to get to s2 to process v
so for every rule A → x in p1 where x is some number of symbols
replace with
A → xS[2]
so we wouldn't choose a grammar to prove this, but I can do it.
S[1] -> .. uS[2] .. uv
P[1]^ = P[1] -
A → x , where x is some number of terminals
union
A→ xS[2] where A→x was an element of P[1]
Let L[1] and L[2] be regular languages
then l[2] intersect L[2] is also regular
this is the one that's not obvious .. union is obvious
(L1 U L2, L*, L^R, L-comp) .. are easy
NFA -> reg exp
example attached
a*b .
a*bab
...
a*b(b*aa*b)*
a*b(b*+aa*b)*
stay on q0, b = qo to q1
can stay on q0 or
go to q0 and stey stere for awhile and then go to q1 for a b
see attached for daigram D
where r[1] is a regular expression
r1*r2(r4 + r3r1*r2)*
if I get down to 2, then, I can read it off
generalized transition graph
: where the edges are labeled with regular expression
complete generalized transition graph - all edges present
how do you go from an nfa to a complete generalized transition graph and then how to reduce it
NFA → complete generalized transition graph
- reduce 1 state at a time until there are two
and then we read it off
Essential that the NFA has one final state because that's the guy we want left .. start state and final state
but that's not an issue .. because we have λ
and that one stateness is why we say we start with an nfa
example attached.
need a complete graph .. so connect or exaple q0 to 02 .. use the empty set .. because it accepts nothing
If there are V states, I must have v^2 edges in theis complete graph
want to say " if you don't see it, it's an empty set"
wanna rip out one at a time.
here's the idea with three states -- attached
remove q[k] but don't want to lose any info
need to give:
the regular expressions for i to j, i to i j to i and j to j
and they must reflect the idea of whether im using k only or not
ii = rii* + rik(rkk)*rki
would never get to i by going from both k and j
i to j = rij + rik*rkj
j to i = rji _ rjk rkk* rki
j to j = rjj* + rjk rkk* rkj
and then redraw the graph with two
with these new regular expressions
so not the most efficient .. but what helps us out is all the @#%@ empty sets
r + empty = empty
rempty = empty
empty* = λ
because L* = {l0, l1, l2 ....} but l0 is always λ
now lets do the big guy
remove q2
(0,0) = empty + empty b* empty = nothing! (empty)
(0,1) = (a+b) + empty b* empty = a+b
(0,3) = nothing
(0,4) = nothing
(1,1) = nothign
(1,0) = nothing
(1,3) = a + bb*empty = a
(1,4) = empty + bb*λ = bb*
(3,3) = a
(3,0) = empty
(3,1) = empty
(3,4) = λ
(4,4) = empty
(4,0) = mepty
(4,1) = empty
(4,3) = empty
see drawing
now rip out 1 or 3
rem 3
rem 1
ended up with
(a+b)bb* + (a+b)aa*
painful but the work gets less each time.