```Homework #4

1.  Construct a DFA equivalent to the NFA defined by
({p,q,r,s}, {0,1}, delta, p, {s}), where delta is defined by
the chart below.

| 0   1
-+--------
p|p,q  p
q| r   r
r| s   -
s| s   s

Solution:  The equivalent DFA is defined by
({{},p,q,r,s,pq,pr,ps,qr,qs,rs,pqr,pqs,prs,qrs,pqrs}, {0,1},
delta', p, {s,ps,qs,rs,pqs,prs,qrs,pqrs}), where delta' is defined
by the chart below.

| 0    1
----+---------
{}| {}   {}
p| pq    p
q|  r    r
r|  s   {}
s|  s    s
pq| pqr  pr
pr| pqs   p
ps| pqs  ps
qr| rs    r
qs| rs   rs
rs|  s    s
pqr|pqrs  pr
prs| pqs  ps
qrs|  rs  rs
pqrs|pqrs prs

2.  Construct a finite automata equivalent to the regular expression
(1 v 01 v 001)* (e v 0 v 00).

Solution:

e
+--------------------------------------------+
|                                            |
|     e   +-+ 1  +-+            e            |
|  +----->| |--->| |--------------------+    |
v /       +-+    +-+                    v    |
+-+    e   +-+ 0  +-+ 1  +-+     e      +-+---+e +-+
--->| |------->| |--->| |--->| |----------->| |----->| |-----+
+-+        +-+    +-+    +-+            +-+      +-+     |
| \   e   +-+ 0  +-+ 0  +-+ 1  +-+   e  ^        ^      |
|  +----->| |--->| |--->| |--->| |------+        |      |
|         +-+    +-+    +-+    +-+               |      |
|                     e                          |      |
+------------------------------------------------+      |
|
+-------------------------------------------------------------+
|
|           e   +-+ e  +-+    e
|        +----->| |--->| |-----------+
|       /       +-+    +-+           v
|    +-+    e   +-+ 0  +-+    e    +===+
+--->| |------->| |--->| |-------->|| ||
+-+        +-+    +-+         +===+
\   e   +-+ 0  +-+ 0  +-+  e ^
+----->| |--->| |--->| |----+
+-+    +-+    +-+

3.  Construct a regular expression for the state diagram shown below.

0           1
+---+        +-+
|   |        | |
v   |        v |
+===+   1    +-+
-->||A||------->|B|
+===+        +-+
^          | ^
|        0 | | 1
|          v |
|     0    +-+
+----------|C|
+-+

Solution:  Let A = state 1, B = state 2, C = state 3.  Then L(M) = R_{11}^3.

R_{11}^3 = R_{11}^2 v R_{13}^2(R_{33}^2)*R_{31})^2

R_{11}^2 = R_{11}^1 v R_{12}^1 (R_{22}^1)* R_{21}^1
R_{11}^1 = R_{11}^0 v R_{11}^0 (R_{11}^0)* R_{11}^0
= (0 v e) v ((0 v e) (0 v e)* (0 v e))
R_{12}^1 = R_{12}^0 v R_{11}^0 (R_{11}^0)* R_{12}^0
= 1 v (0 v e)(0 v e)*1
R_{22}^1 = R_{22}^0 v R_{21}^0 (R_{11}^0)* R_{12}^0 = (1 v e)
R_{21}^1 = R_{21}^0 v R_{21}^0 (R_{11}^0)* R_{11}^0 = empty
R_{11}^2 = (0 v e) v ((0 v e) (0 v e)* (0 v e))

R_{13}^2 = R_{13}^1 v R_{12}^1 (R_{22}^1)* R_{23}^1
R_{13}^1 = R_{13}^0 v R_{11}^0 (R_{11}^0)* R_{13}^0 = empty
R_{23}^1 = R_{23}^0 v R_{21}^0 (R_{11}^0)* R_{13}^0 = 0
R_{13}^2 = (1 v (0 v e)(0 v e)*1)(1 v e)* 0

R_{33}^2 = R_{33}^1 v R_{32}^1 (R_{22}^1)* R_{23}^1
R_{33}^1 = R_{33}^0 v R_{31}^0 (R_{11}^0)* R_{13}^0 = e
R_{32}^1 = R_{32}^0 v R_{31}^0 (R_{11}^0)* R_{12}^0 = 1 v 0(0 v e)* 1
R_{33}^2 = e v (1 v 0(0 v e)*1)(1 v e)*0

R_{31}^2 = R_{31}^1 v R_{32}^1 (R_{22}^1)* R_{21}^1
R_{31}^1 = R_{31}^0 v R_{31}^0(R_{11}^0)*R_{11}^0 = 0 v 0(0 v e)*(0 v e)
R_{31}^2 = 0 v 0(0 v e)*(0 v e)

R_{11}^3 = [(0 v e) v ((0 v e) (0 v e)* (0 v e))] v
[((1 v (0 v e)(0 v e)*1)(1 v e)* 0)
(e v (1 v 0(0 v e)*1)(1 v e)*0)*
(0 v 0(0 v e)*(0 v e))]

= 0* v [0*1 v 0(0*1+0)*0*]

4.  Which of the following languages are regular sets?  Prove your answer.
a) L1 = {0^{2n} | n >= 1}
b) L2 = {0^p 1^q 0^{p+q} | m >= 1 and n >= 1}
c) L3 = {x x^R: x in (0 v 1)+}
d) L4 = The set of all strings in (0 v 1)+ that do not contain the
substring 010.

Solution:
a) Regular.  Here is a finite state machine that accepts the language.

0
+-----------+
|           |
v           |
+-+   0    +-+   0    +===+
--->| |------->| |------->|| ||
+-+        +-+        +===+

b) Nonregular.  Assume that L2 is regular.  By the pumping lemma, there is a
constant n such that for any z in L2, |z| >= n, we can break z into u, v,
and w such that |uv| <= n, |v| >= 1, and know that uv^iw is in L2 for all
i >= 0.  We pick z to be 0^n 1^n 0^{2n}.  For this string, u and v will
be within the first segment of 0s.  Let u = 0^s and v = 0^t, where
s+t <= n and t >= 1.  The pumping lemma claims that
0^s 0^{i*t} 0^{n-s-t} 1^n 0^{2n} is in L2.  When i = 0 this is not true
because the string will be 0^{n-t} 1^n 0^{2n}, and n-t does not equal n
because t >= 1.  Thus the language is not regular.

c) Nonregular.  Assume that L3 is regular.  By the pumping lemma, there is a
constant n such that if z is in L3, |z| >= n, then there exists u, v, w
such that |uv| <= n, |v| >= 1, z = uvw and uv^iw is in L3 for all i >= 0.
Let z = 1^n 00 1^n.  With this selection, both u and v are within the
first segment of 1s.  Let u = 1^s and v = 1^t, where s + t <= n and
t >= 1.  The pumping lemma claims that 1^s 1^{i*t} 1^{n-s-t} 00 1^n is in
L3.  This is not true:  if i = 0, the resulting string is 1^{n-t} 00 1^n,
which is not in the language L3.

d) Regular.  It is easy to generate a finite state machine that accepts
the complement of L4 (all strings containing 010), as shown below.

+-+   0    +-+   1    +-+   0    +===+
--->| |------->| |------->| |------->|| ||
+-+        +-+        +-+        +===+

Because we have shown that L4 complement is regular, and we know that
regular sets are closed under complementation, we then know that L4
is regular.

5.  Use the pumping lemma to prove that language L defined below is not
regular.

L = {ww^c:  w in {a,b}*}, where w^c stands for w with each occurrence of a
replaced by b, and vice versa.

Solution:  You should be able to sense that this is nonregular, because it
would be necessary to remember the first half of the string in order to be
able to check whether the second half is the corresponding
symbol-by-symbol complement.  That would require an amount of memory linear
in the size of the input string, while only a constant amount
of memory is available in a DFA.

Recall we showed in class that the language 0^k 1^k, k>= 0, is nonregular.
The same argument can be used to show that a^k b^k is nonregular.
If we generate the intersection of the language in question L with
the known regular language a*b* we obtain the language a^k1^k, k>= 0.
Because the resulting language is not regular and regular languages are
closed under intersection, the language in question is not regular.

6.  Are the following statements true or false?  Explain your answer in each
case.

Solution:

a) False.  We will show this by contradiction.  We know that the language
L1 = 0*1* is regular.  We also know that the language L2 = 0^n1^n , n>=0,
is a subset of L1 because every string in L2 is in L1.  However, we have
proven in class that L2 is not regular, so regular languages are not
closed under subset.

c) True.  We know that L is regular.  We also know that the set of all
strings not in L, the complement of L (L_c) is regular because regular
languages are closed under complementation.  We are then considering the
concatenation of two regular languages which we have shown in class to
be regular.

e) True.  If L is a regular language, then there exists an NFA that
recognizes strings in L.  We can use this NFA to construct an NFA
for the language in question, L'.

7.  Simulate your constructed DFA from problem 1 using the DFA simulator
available at http://ranger.uta.edu/~cook/tcs/fsm/Simulator.html
Turn in a picture of the constructed DFA.  You will need a browser capable
of running Java applets to complete this homework problem.
```