Assignment #4: Minimizing DFA

Due Date: August 3, 2007

EXERCISES

1. Construct DFA's for the regular expression "(a|b)*abb(a|b)*" using Algorithm 3.5 (Construction of a DFA from a regular expression r).

2. Minimize the states in the DFA's of Exercise 1 using Algorithm 3.6 (Minimizing the number of states of a DFA).

Laboratory Exercises Listing and Download

Click to download laboratory exercises from 1 through 4:

• Laboratory No. 1 - Writing a Simple Scanner.pdf

• Laboratory No. 2 - Patterns and Lexical Analysis.pdf

• Laboratory No. 3 - Programming Using LEX.pdf

• Laboratory No. 4 - Regular Expression to Deterministic Finite Automata.pdf

Groupings and Guidelines: Laboratory No. 4

Here are the list of groupings for the Laboratory No. 4:

Group No. 1
Bolongan, James S.
Conejos, Farrell John T.
Mira, Ken Rothwyn M.

Group No. 2
Buot, Ma. Adelaida A.
Luna, Charlie Louie E.
Monte, Divine Grace O.

Group No. 3
Oriente, Jerry Paulo S.
Par, Mary Jane A.
Tupac, Arnold Jansen U.


Guidelines:

• Deadline for this machine problem will be on August 15, 2007.

• Each of the group will submit a hard copy of the source code written in their chosen programming language with a documentation. The documentation must explain the semantic of every class, method, function and any part of the source code.
• Hard copy specification:
• computerized (word-processor-application-generated)
• printed in short bond paper
  
• text:
• font: Garamond
• size: 12 pt.
• source code:
• font: Courier
• size: 10 pt.
• test suite (input/output) with at least 10 examples

• The group will defend their work. If no member could answer the questions given, a point will be deducted from the total score.
• The group will prepare a presentation. It should be created in OpenOffice.org Impress.
• Each of the member of the group will present and will be asked.

Deadline: Laboratory No. 3

Deadline for the submission of Laboratory No. 3 will be on July 31, 2007.

No submission will be accepted beyond that date and will be given a score of zero.

First Preliminary Examination 2

Our preliminary exam this coming Friday, July 20, 2007 is moved on July 24, 2007. We still don't have a class this coming Friday.

First Preliminary Examination

The CSc 153 class will not meet on Tuesday, July 17, 2007.

CSc 153's first preliminary exam will be on Friday, July 20, 2007. Bring your own test booklet, ball pen (black or blue), and extra money for your test questionnaire.

Coverage of the preliminary exam are the following:

• Introduction to Compiling (Chapter 1)
  
• Lexical Analysis (Chapter 3)
• A Simple Compiler (Chapter 2)
  

Possible exam types:

• Modified True of False
• Multiple Choice
• Identification
• Fill in the Blanks
• Enumeration
• Problem Solving

Note: I am not giving you a special exam except for those who have a valid reason.

Lex Example: A C Comment Recognizer

The following is a lex program that will recognize a multi-line comment in C:

---Program Starts Here---

%option noyywrap

sc        "/*"
ec        "*/"
string    \"[^"]*\"
inside    [^*]|"*"[^/]|{string}
comment    {sc}{inside}*{ec}

%%

{comment}    {    printf("<<<%s>>>", yytext);    }
.            {    printf("%s", yytext);    }

%%

int main ()
{
 yylex();
 return 0;
}

---Program Ends Here---

Note: Check your google group. I uploaded the flex and bison binary files.

Assignment #3

Points: 20 pts.
Due Date: July 10, 2007/3:00 PM

RE = (ab|ba)[c-z0-9]*(ab|ba)

1. Create a nondeterministic finite automaton or NFA that will accept a string that is a member of the language generated by L(RE).

2. Convert your NFA N from your exercise 1 into an equivalent DFA D.