Description
Problem 1. (30 points)
Find the language recognized by the given DFA:
1.
start s0 s1
s2
1
0
0,1
0
1
2.
start s0 s1
s2
0
1
1
0
0,1
3.
start s0 s1 s2 s3
0
1 0
1 0,1
0,1
Solution.
1.
(0, 1)∗ From s1
λ From s0
L(m) =1(0, 1)∗
λ
1
2.
1
∗
from s2
λ from s0
L(m) =01∗
| λ
3.
1
∗
0 from s0
0+ from s1
(0, 1)+ from s3
L(m) =1∗
0
+ | 1
∗
0
+1(0, 1)+
2
Problem 2. (20 points)
Show that the following grammar generates the language {a
nb
nc
n | n ≥ 0}.
S ::= aST | λ
T ::= BC
CB ::= BC
aB ::= ab
bB ::= bb
bC ::= bc
cC ::= cc
Solution.
S ::= aST | λ from this it can be seen the case when n = 0 for a, b, c is true. Also, if not (1)
λ the S string will continue to repeat itself thus the string must start with a
n
(2)
a
nB
nC
n
from T ::= BC (3)
a
n
b
nC
n
from aB ::= ab (4)
a
n
b
n
c
n
from bC ::= bc (5)
Aggie Honor Statement: On my honor as an Aggie, I have neither given nor received any unauthorized
aid on any portion of the academic work included in this assignment.
Checklist: Did you…
1. abide by the Aggie Honor Code?
2. solve all problems?
3. start a new page for each problem?
4. show your work clearly?
5. type your solution?
6. submit a PDF to eCampus?
3
Powered by TCPDF (www.tcpdf.org)
