Exam 1 -- summary (wording may have changed slightly)
1. Give regular expressions for
	a. Strings of a's and b's that start and/or end with b
	b. Strings of a's and b's that start and end with b
	c. Strings of a's and b's that start or end with b but do not start and end with b
	d. Non-zero length strings of digits in {1,2,3} such that digits occur in descending order.
	e. Strings of 0's and 1's that do not contain the substring 00
2. Show CFG is ambiguous
	S-> bSS | SS a | a | b
3. Construct DFA for regular expression 
	ab(a|b)*ba
4. Give regular expression for the NFA
	State 0: empty goes to state 1
	State 1: y goes to state 3
	State 2: x goes to state 1
	State 3: y goes to state 2
	State 3: z goes to state 1
	start state = 0
	accept states = {3}
5. Give DFA for the NFA
	State 0: empty goes to state 1
	State 0: empty goes to state 2
	State 1: y goes to state 3
	State 2: x goes to state 1
	State 2: x goes to state 3
	State 3: y goes to state 2
	State 3: z goes to state 1
	start state = 0
	accept states = {3}
6. Rewrite CFG with precedence and associativity approppriate.
	E => E or E |  E and E | num R num | B
	R => < | >
	B => t | f
================================================================
Solutions
	Exam 1 -- summary (wording may have changed slightly)
1. Give regular expressions for
	a. Strings of a's and b's that start and/or end with b
b (a|b)* | (a|b)* b
	b. Strings of a's and b's that start and end with b
b (a|b)* b | b
	c. Strings of a's and b's that start or end with b but do not start and end with b
b (a|b)* a | a (a|b)* b
	d. Non-zero length strings of digits in {1,2,3} such that digits occur in descending order.
3+ 2* 1* | 2+ 1* | 1+
	e. Strings of 0's and 1's that do not contain the substring 00
0? (1 0?)*
2. Show CFG is ambiguous
	S-> bSS | SSa | a | b
		baa
S      		or		S
bSS 				SSa
baS 				bSa
baa 				baa
3. Construct DFA for regular expression 
	ab(a|b)*ba
s0: 	ref: ^ab(a|b)*ba$
	on a goto s1 
s1: 	ref: a^b(a|b)*ba$
	on b goto s2 
s2: 	ref: ab^(a|b)*ba$
	on a goto s2
	on b goto s3
s3: 	ref: ab(a|b)*b^a$
	on a goto s4
	on b goto s3
s4: 	ref: ab(a|b)*ba^$
	on a goto s2
	on b goto s3
	(on $ accept)
start state = s0
accept states = {s4}

4. Give regular expression for the NFA
	State 0: empty goes to state 1
	State 1: y goes to state 3
	State 2: x goes to state 1
	State 3: y goes to state 2
	State 3: z goes to state 1
	start state = 0
	accept states = {3}
-----------------------------------
Answer: (yy x | yz)* y
-----------------------------------
Method: 
-----------------------------------
S0:
	S1
S1: 
	y S3
S2:
	x S1
S3:
	y S2
	z S1
	$ (accept)
-----------------------------------
S0:
	S1
S1: 	y S3 becomes 
	yy S2
	yz S1
	y$ (accept)
S2:
	x S1
-----------------------------------
S0:
	S1
S1: 	
	yy x S1
	yz S1
	y$ (accept)
-----------------------------------
S0:
	S1
S1: 	
	(yy x | yz)* y$ (accept)
-----------------------------------
(yy x | yz)* y

5. Give DFA for the NFA
	State 0: empty goes to state 1
	State 0: empty goes to state 2
	State 1: y goes to state 3
	State 2: x goes to state 1
	State 2: x goes to state 3
	State 3: y goes to state 2
	State 3: z goes to state 1
	start state = 0
	accept states = {3}
__________________________
Method:
S0:
	emove S1
	emove S2
S1
	y goto S3
S2
	x goto S1
	x goto S3
S3
	y goto S2
	z goto S1
__________________________
S0 emove {S1 S2} leads to 
State {S0 S1 S2}
	y goto {S3}
	x goto {S1 S3}
State {S3}
	y goto {S2}
	z goto {S1}
State {S1 S3}
	y goto {S2 S3}
	z goto {S1}
State {S2 S3}
	x goto {S1 S3}
	y goto {S2}
	z goto {S1}
State {S2}
	x goto {S1 S3}
State {S1}
	y goto {S3}
start state = {S0 S1 S2}
accept states = {{S3} {S1 S3} {S2 S3}}

	
6. Rewrite CFG with precedence and associativity approppriate.
	E => E or E |  E and E | num R num | B
	R => < | >
	B => t | f
Solution:
E => E or T | T
T => T and F | F
F => num R num | B
R => < | >
B => t | f