TWiki> CS301 Web>Syllabus>Homeworks>ProblemSet3 (revision 1)EditAttach

CS 301, Spring 2012, Problem Set 3

1 DFA

Construct DFA's for the following languages:

  1. L = \{ w \in \{0, 1\}^*:\: all \: strings \: with \: at \: least \: one \: 0 \:and \: exactly \: two \: 1's \}.
  2. L = \{w \in \{0,1\}^* : \:all\: strings \: with \: the \: number \: of \: 1's\: mod \:4 = 0 \}.
  3. The set of all strings with at most two substrings of 000's.
  4. The set of all strings that start or end with 01.
  5. The set of all strings with at least 3 0's and at most 2 1's.
  6. The set of all strings in which the di erence between the number of 1's and number of 0's is any prefi x is within the range [-2,2].
  7. The set of all strings of the form 11x, where x contains an even number of 0's.

2 NFA

Construct NFA's for the following languages:

  1. The set of strings of 0's and 1's such that any two 0's separated by a number of positions that is a multiple of 3.
  2. Construct an NFA with no more than 5 states for L = \{ 0101^n : n \geq 0 \} \cup \{ 010^n : n \geq 0\}.
  3. Construct an NFA for the language speci ed by the regular expression: (10 \cup 11)^* \cup (01 \cup 00)^*.
More questions to come.
Edit | Attach | Print version | History: r5 | r4 < r3 < r2 < r1 | Backlinks | Raw View | Raw edit | More topic actions...
Topic revision: r1 - 2012-01-24 - 00:50:12 - Main.hhabib3
 
Copyright 2016 The Board of Trustees
of the University of Illinois.webmaster@cs.uic.edu
WISEST
Helping Women Faculty Advance
Funded by NSF