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.