2.1
a. [ac]*a[abc]* | c*
b. ((a[bc]*a)|[bc]*)*
c. [10]*00|0
d. [01]*1[01]{6,}|(0*11[01]{4}|1011[01]{2}|101010|101011)
e. a*(b(?a)|ca*)*
f. [1-9][0-9]* | 0[1-7][0-7]*
g. 2
2.2
a. Because in the regular expression, there is no way to store that how many times a letter occurs, so we can't determine whether the count of a is larger than b.
b. equally, in the regular expression, we also can't know what have occurred before.
c. In the C programming language, there are some rules like the parenthesis, But in the regular language, we can't determine whether the parenthesis is right. Therefore, we can't use the regular language to determine whether a C program is right or not.
2.5
a.
DFA
b. Because there are too many states in this DFA, so I only write down the processing procedure and get all of the state. And I get this result by writing a Java program, and i put the Java program in the appendix. The result shows below.
- DFAedge({1}, a) -> {1, 2}
- DFAedge({1}, b) ->{1}
- DFAedge({1, 2}, a) -> {1, 2, 3}
- DFAedge({1, 2}, b) ->{1, 3}
- DFAedge({1, 2, 3}, a) -> {1, 2, 3, 4}
- DFAedge({1, 2, 3}, b) ->{1, 3, 4}
- DFAedge({1, 3}, a) -> {1, 2, 4}
- DFAedge({1, 3}, b) ->{1, 4}
- DFAedge({1, 2, 3, 4}, a) -> {1, 2, 3, 4, 5}
- DFAedge({1, 2, 3, 4}, b) ->{1, 3, 4, 5}
- DFAedge({1, 3, 4}, a) -> {1, 2, 4, 5}
- DFAedge({1, 3, 4}, b) ->{1, 4, 5}
- DFAedge({1, 2, 4}, a) -> {1, 2, 3, 5}
- DFAedge({1, 2, 4}, b) ->{1, 3, 5}
- DFAedge({1, 4}, a) -> {1, 2, 5}
- DFAedge({1, 4}, b) ->{1, 5}
- DFAedge({1, 2, 3, 4, 5}, a) -> {1, 2, 3, 4, 5, 6}
- DFAedge({1, 2, 3, 4, 5}, b) ->{1, 3, 4, 5, 6}
- DFAedge({1, 3, 4, 5}, a) -> {1, 2, 4, 5, 6}
- DFAedge({1, 3, 4, 5}, b) ->{1, 4, 5, 6}
- DFAedge({1, 2, 4, 5}, a) -> {1, 2, 3, 5, 6}
- DFAedge({1, 2, 4, 5}, b) ->{1, 3, 5, 6}
- DFAedge({1, 4, 5}, a) -> {1, 2, 5, 6}
- DFAedge({1, 4, 5}, b) ->{1, 5, 6}
- DFAedge({1, 2, 3, 5}, a) -> {1, 2, 3, 4, 6}
- DFAedge({1, 2, 3, 5}, b) ->{1, 3, 4, 6}
- DFAedge({1, 3, 5}, a) -> {1, 2, 4, 6}
- DFAedge({1, 3, 5}, b) ->{1, 4, 6}
- DFAedge({1, 2, 5}, a) -> {1, 2, 3, 6}
- DFAedge({1, 2, 5}, b) ->{1, 3, 6}
- DFAedge({1, 5}, a) -> {1, 2, 6}
- DFAedge({1, 5}, b) ->{1, 6}
- DFAedge({1, 2, 3, 4, 5, 6}, a) -> {1, 2, 3, 4, 5, 6}
- DFAedge({1, 2, 3, 4, 5, 6}, b) ->{1, 3, 4, 5, 6}
- DFAedge({1, 3, 4, 5, 6}, a) -> {1, 2, 4, 5, 6}
- DFAedge({1, 3, 4, 5, 6}, b) ->{1, 4, 5, 6}
- DFAedge({1, 2, 4, 5, 6}, a) -> {1, 2, 3, 5, 6}
- DFAedge({1, 2, 4, 5, 6}, b) ->{1, 3, 5, 6}
- DFAedge({1, 4, 5, 6}, a) -> {1, 2, 5, 6}
- DFAedge({1, 4, 5, 6}, b) ->{1, 5, 6}
- DFAedge({1, 2, 3, 5, 6}, a) -> {1, 2, 3, 4, 6}
- DFAedge({1, 2, 3, 5, 6}, b) ->{1, 3, 4, 6}
- DFAedge({1, 3, 5, 6}, a) -> {1, 2, 4, 6}
- DFAedge({1, 3, 5, 6}, b) ->{1, 4, 6}
- DFAedge({1, 2, 5, 6}, a) -> {1, 2, 3, 6}
- DFAedge({1, 2, 5, 6}, b) ->{1, 3, 6}
- DFAedge({1, 5, 6}, a) -> {1, 2, 6}
- DFAedge({1, 5, 6}, b) ->{1, 6}
- DFAedge({1, 2, 3, 4, 6}, a) -> {1, 2, 3, 4, 5}
- DFAedge({1, 2, 3, 4, 6}, b) ->{1, 3, 4, 5}
- DFAedge({1, 3, 4, 6}, a) -> {1, 2, 4, 5}
- DFAedge({1, 3, 4, 6}, b) ->{1, 4, 5}
- DFAedge({1, 2, 4, 6}, a) -> {1, 2, 3, 5}
- DFAedge({1, 2, 4, 6}, b) ->{1, 3, 5}
- DFAedge({1, 4, 6}, a) -> {1, 2, 5}
- DFAedge({1, 4, 6}, b) ->{1, 5}
- DFAedge({1, 2, 3, 6}, a) -> {1, 2, 3, 4}
- DFAedge({1, 2, 3, 6}, b) ->{1, 3, 4}
- DFAedge({1, 3, 6}, a) -> {1, 2, 4}
- DFAedge({1, 3, 6}, b) ->{1, 4}
- DFAedge({1, 2, 6}, a) -> {1, 2, 3}
- DFAedge({1, 2, 6}, b) ->{1, 3}
- DFAedge({1, 6}, a) -> {1, 2}
- DFAedge({1, 6}, b) ->{1}
2.6
-
the state 8 and the state 2 is equal.
Step 1 -
the state 5 and the state 1 is equal
Step 2 -
the state 4 and the state 6 is equal
Step 3
The last five states are all different, so, the minimum number of states is 5.
Appendix
import java.util.Vector;
public class Test {
public static void main(String argv[]) {
int []a = new int[200];
//initialize the array which can determine whether a state occur or not
for(int i = 0; i < 200; i++)a[i] = -1;
state g1;
Vector<state> q;
//Use an algorithm like BFS to go through all the edge
q = new Vector<state>();
//BFS from the initial state
g1 = new state();
g1.s[1] = true;
q.add(g1);
while (q.size() != 0) {
int count = 0, k = 0;
//the new state with the input a and b
state s1 = new state(), s2 = new state();
state tmp = q.firstElement();
q.remove(0);
//determine whether this state occur before
for(int i = 1; i < 7; i++){
if(tmp.s[i] == true)count += i*i*i*i*i;
}
for(k = 0; k < 200; k++){
if(a[k] == -1 || count == a[k])break;
}
if(a[k] != -1)continue;
else a[k] = count;
//set the next two states
if (tmp.s[1] == true) {
s1.s[1] = true;
s1.s[2] = true;
s2.s[1] = true;
}
for (int i = 2; i < 6; i++) {
if (tmp.s[i] == true) {
s1.s[i + 1] = true;
s2.s[i + 1] = true;
}
}
q.addElement(s1); q.addElement(s2);
//output the result
System.out.print("+ DFAedge({");
for(k = 1; k < 7; k++){
if(tmp.s[k] == true){
System.out.printf("%d", k);
break;
}
}
for (int i = k + 1; i < 7; i++) {
if (tmp.s[i] == true) System.out.printf(", %d", i);
}
System.out.printf("}, a) -> {");
for(k = 1; k < 7; k++){
if(s1.s[k] == true){
System.out.printf("%d", k);
break;
}
}
for (int i = k + 1; i < 7; i++) {
if (s1.s[i] == true) System.out.printf(", %d", i);
}
System.out.printf("}\n+ DFAedge({");
for(k = 1; k < 7; k++){
if(tmp.s[k] == true){
System.out.printf("%d", k);
break;
}
}
for (int i = k + 1; i < 7; i++) {
if (tmp.s[i] == true) System.out.printf(", %d", i);
}
System.out.printf("}, b) ->{");
for(k = 1; k < 7; k++){
if(s2.s[k] == true){
System.out.printf("%d", k);
break;
}
}
for (int i = k + 1; i < 7; i++) {
if (s2.s[i] == true) System.out.printf(", %d", i);
}
System.out.print("}\n");
}
}
}
//store one state in the DFA
class state{
public boolean [] s = new boolean[7];
public state(){s[0] = s[1] = s[2] = s[3] = s[4] = s[5] = s[6] = false;}
}
