# Ambrose Sterr 02/01/06
# | = union/or
# ~ = espilon
# The first one that came with a picture
# L = {(a|(b(a|ba)*bb))*(~|(b(b|ba)*b))}
states: [1,2,3]
alphabet: [a,b]
start: 1
accept: [1,2]
transitions:
-[1,a,1]
-[1,b,3]
-[2,a,3]
-[2,b,1]
-[3,a,3]
-[3,b,2]
inputs:
-[a,b,a,b,a,b,a,b]
-[a,a,a]
-[b,b,b]
-[a,a,b,b,a,a,b,b]
---
# The second one that came with a picture
# L = {((~|(ab*(a|b)))a)*(~|(ab*(a|b)))
states: [1,2,3]
alphabet: [a,b]
start: 1
accept: [2]
transitions:
-[1,~,2]
-[1,a,3]
-[2,a,1]
-[3,a,2]
-[3,b,2]
-[3,b,3]
inputs:
-[a,b,a,b,a,b,a,b]
-[a,a,a]
-[b,b,b]
-[a,a,b,b,a,a,b,b]
---
# Provide a DFA that recognizes La = { w | w begins with 1 and ends with 0}
states: [1,2,3,4]
alphabet: [0,1]
start: 1
accept: [3]
transitions:
-[1,0,4]
-[1,1,2]
-[2,0,3]
-[2,1,2]
-[3,0,3]
-[3,1,2]
-[4,0,4]
-[4,1,4]
tests:
-[Yes [1,0,0]]
-[No []]
-[No [0,0,0]]
-[Yes [1,0]]
---
# Provide a DFA that recognizes Lb = { w | w contains an even number of 0's or exactly two 1's}
states: [1,2,3,4,5,6,7,8]
alphabet: [0,1]
start: 1
accept: [1,3,5,6,7]
transitions:
-[1,0,2]
-[1,1,3]
-[2,0,1]
-[2,1,4]
-[3,0,4]
-[3,1,5]
-[4,0,3]
-[4,1,6]
-[5,0,6]
-[5,1,7]
-[6,0,5]
-[6,1,8]
-[7,0,8]
-[7,1,7]
-[8,0,7]
-[8,1,8]
tests:
-[Yes [1,1,1]]
-[Yes []]
-[No [0,1]]
-[Yes [1,0,0,0,1]]
-[No [1,0,1,0,1,0]]
---
# Provide an NFA that recognizes Lc = { w | w contains 1100 or does not contain 1010}
states: [1,2,3,4,5,6,7,8,9,10,11]
alphabet: [0,1]
start: 1
accept: [6,7,8,9,10]
transitions:
-[1,~,2]
-[1,~,7]
-[2,0,2]
-[2,1,2]
-[2,1,3]
-[3,1,4]
-[4,0,5]
-[5,0,6]
-[6,0,6]
-[6,1,6]
-[7,0,7]
-[7,1,8]
-[8,0,9]
-[8,1,8]
-[9,0,7]
-[9,1,10]
-[10,0,11]
-[10,1,8]
-[11,0,11]
-[11,1,11]
tests:
-[Yes [1,1,1]]
-[Yes []]
-[No [0,1,1,0,1,0,1,1,1,1]]
-[Yes [1,0,0,0,1]]
-[Yes [1,1,0,0,1,0,1,0]]