| |
CS3723. Programming Languages, Fall2013
Recitation 3, Paritial Answers
Part A.
Regular Expression: /a(ab)*|b(ba)*/
RE in BNF form: aab+*+bba+*+|$
NFA with eps-moves recognizing above RE:
0 --> [a, 1]
1 --> [@, 6]
2 --> [a, 3]
3 --> [@, 4]
4 --> [b, 5]
5 --> [@, 2] --> [@, 7]
6 --> [@, 7] --> [@, 2]
7 --> [@,17]
8 --> [b, 9]
9 --> [@,14]
10 --> [b,11]
11 --> [@,12]
12 --> [a,13]
13 --> [@,10] --> [@,15]
14 --> [@,15] --> [@,10]
15 --> [@,17]
s 16 --> [@, 8] --> [@, 0]
t 17 -->
Simulation with input string: aabababa$
| 1 1 1 1 1 1 1 1
| 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7
| - - - - - - - - - - - - - - - - - -
: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 s
: 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 s
a: 0 1 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 1 t
a: 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0
b: 0 0 1 0 0 1 0 1 0 0 0 0 0 0 0 0 0 1 t
a: 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0
b: 0 0 1 0 0 1 0 1 0 0 0 0 0 0 0 0 0 1 t
a: 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0
b: 0 0 1 0 0 1 0 1 0 0 0 0 0 0 0 0 0 1 t
a: 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0
Simulation with input string: bbababaa$
| 1 1 1 1 1 1 1 1
| 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7
| - - - - - - - - - - - - - - - - - -
: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 s
: 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 s
b: 0 0 0 0 0 0 0 0 0 1 1 0 0 0 1 1 0 1 t
b: 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0
a: 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 0 1 t
b: 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0
a: 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 0 1 t
b: 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0
a: 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 0 1 t
a: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
DFA:
+----------------+------------------+
| a | b |
+==================+================+==================+
| cl({16}) = | cl{{1}) = | cl({9} = |
| {0,8,16} | {1,2,6,7,17} | {9,10,14,15,17} |
+------------------+----------------+------------------+
| {1,2,6,7,17} | cl({3}) = | empty |
| | {3,4} | |
+------------------+----------------+------------------+
| {9,10,14,15,17} | empty | cl({11}) = |
| | | {11,12} |
+------------------+----------------+------------------+
| {3,4} | empty | cl({5} = |
| | | {2,5,7,17} |
+------------------+----------------+------------------+
| {11,12} | cl({13} = | empty |
| | {10,13,15,17} | |
+------------------+----------------+------------------+
| {2,5,7,17} | cl({3}) = | empty |
| | {3,4} | |
+------------------+----------------+------------------+
| {10,13,15,17} | empty | cl({11}) = |
| | | {11,12} |
+------------------+----------------+------------------+
| empty | empty | empty |
+------------------+----------------+------------------+
Part B.
1.a. {anbcn: n>=0}, or
any number of a's followed by 1 b,
followed by the same number of cs as as.
(This language cannot be recognized by any finite automaton.)
1.b. Any odd number of a's. (O stands for "odd, E for "even".)
1.c. Any string of 1 or more a's.
1.d. Any string of 1 or more letters a through d, enclosed in
parens, and with any two letters separated by a comma.
1.e. {am(bc)n: m>=1, n>=1},
Where the parens are metasymbols.
2, 3, 4, 5: I hope these are straightforward now.
5.a. and 5.b. Any sequence of "balanced parentheses".
Not trivial to prove.
5.c. All strings with the same number of a's and b's.
Here's another similar grammar that generates the same language:
S ---> aSb | bSa | SS | epsilon
(It's hard to see that this is true, and hard to prove it.)
|