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

CS 301, Spring 2012, Problem Set 3

Instructions for submission:
Construct the DFAs and NFAs for the following problems using JFLAP, and turn in your automata using the blackboard. There is a folder with the name Problem Set 3, you can attach and submit your .jff or zipped files through that.
The submission through this folder will close on January 27, 2012 at 12:10 PM sharp.

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 fference between the number of 1's and number of 0's in 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: r2 - 2012-01-24 - 17:38:11 - 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