Regular Languages: Answers
  1. This language consists of those strings with precisely one b at the end. This could be rewritten as a*b.

    1. (a|b)*
    2. (a|b)*
    3. (a|b)*
    4. b* a (a|b)*

    1. b* | b*ab* | b*ab*ab* | b*ab*ab*ab*
    2. (b*ab*ab*ab*)*
    3. (b | ab | aab)* aaa (b | ba | baa)*

    1. True
    2. True
    3. False
    4. False

    1. The DFA is as follows:
      State Symbol d(State,Symbol)
      0 a 0
      0 b 0
      where the start state is 0 and the accepting state is 0.

    2. The DFA is as follows:
      State Symbol d(State,Symbol)
      0 a 0
      0 b 0
      where the start state is 0 and the accepting state is 0.

    3. The DFA is as follows:
      State Symbol d(State,Symbol)
      0 a 0
      0 b 0
      where the start state is 0 and the accepting state is 0.

    4. The DFA is as follows:
      State Symbol d(State,Symbol)
      0 a 1
      0 b 0
      1 a 1
      1 b 1
      where the start state is 0 and the accepting state is 1.


    1. The DFA is as follows:
      State Symbol d(State,Symbol)
      0 a 1
      0 b 0
      1 a 2
      1 b 1
      2 a 3
      2 b 2
      3 b 3
      where the start state is 0 and the accepting states are 0, 1, 2 and 3.

    2. The DFA is as follows:
      State Symbol d(State,Symbol)
      0 a 1
      0 b 0
      1 a 2
      1 b 1
      2 a 0
      2 b 2
      where the start state is 0 and the accepting state is 0.

    3. The DFA is as follows:
      State Symbol d(State,Symbol)
      0 a 1
      0 b 0
      1 a 2
      1 b 0
      2 a 3
      2 b 0
      3 b 4
      4 a 5
      4 b 4
      5 a 3
      5 b 5
      where the start state is 0 and the accepting states are 3, 4 and 5.


      1. Yes
      2. Yes
      3. No
      4. Yes

      1. Yes
      2. Yes
      3. Yes
      4. Yes
      5. No

    1. The subset construction method gives the following:
      State Symbol d(State,Symbol)
      0 a {0,1}
      {0,1} a {0,1}
      {0,1} b 1
      1 b 1
      where the start state is 0 and the accepting states are 0 and {0,1}.

    2. The subset construction method gives the following:
      State Symbol d(State,Symbol)
      0 a 1
      1 b {2,3}
      {2,3} a {1,3}
      {1,3} a 1
      {1,3} b {2,3}
      where the start state is 0 and the accepting states are 0, {2,3} and {1,3}.


  9. An NFA to recognise the same language is as follows:
    State Symbol d(State,Symbol)
    0 a 0
    0 b 0
    0 a 1
    1 a 1
    1 b 1
    where the start state is 0 and the accepting state is 1.

    Converting this into an equivalent DFA gives the following:
    State Symbol d(State,Symbol)
    0 a 1
    0 b 0
    1 a 1
    1 b 1
    where the start state is 0 and the accepting state is 1.

  10. In order to prove that a language is not regular using the pumping lemma, we must show that there are strings x, y and z such that |y| > 0 and xykz is an element of the language for all k >= 0. We assume that the language is regular, and obtain a contradiction.
    1. Let s = akbbak. s must equal xyz, where x, y and z satisfy the conditions above. y must consist only of a's, so xy2z cannot be a member of the language.
    2. Let s = akbakb. s must equal xyz, where x, y and z satisfy the conditions above. y must consist only of a's, so xy2z cannot be a member of the language.