Blog: CS402 Assignment No. 2 solution

Theory of Automata (CS402)

Assignment No.2

Deadline

Your assignment must be uploaded before or on 27th April, 2011

Rules for Marking

It should be clear that your assignment will not get any credit if:

• The assignment is submitted after due date

• The assignment is copied

Objectives

Objective of this assignment is to make students able to understand the following concepts,

• Finite Automata

• Transition Graph

• Generalized Transition Graphs

• Kleene’s Theorem Part III

Question No.1

Finite Automata

Consider the Language L of Strings, defined over Σ = {a, b}, staring and ending with same letter. The RE of language is: (a+b) +a (a + b)*a + b (a + b)*b. Draw the FA of given Language.

Question No.2

Transition Graph

Draw the TG for the language L of strings, defined over Σ = {a, b} in which if a occur it is in the form of aaa and that ends in two or more b’s.

Some example strings are:

bb , bbb , bbbbb , … , aaabb , aaabaaabb , baaabaaabb , baaabaaabbbb ,

bbbaaabaaabbbb , …

Question No.3

Transition Graph

Draw the TG for the language L of strings, defined over Σ = {a, b}, beginning and ending in same letters. The language L may be expressed by RE a(a + b)*a + b(a + b)*b.

Question No.4

Generalized Transition Graphs

Consider the language L of strings, defined over Σ = {a,b}, accepting all strings without double “b”. Draw the GTG for the above stated language.

[Hint: First make RE of the language].

Question No.5

Kleene’s Theorem Part III

Let r1 = (a + b)*a and the corresponding FA1 be

Find out the FA corresponding to r1+ r2

How to Make FA using Word:

You can view the video file

http://vulms.vu.edu.pk/Courses/CS402/Downloads/Assignment1.00.zip

to see how to make FA in MS Word.

Important Note:

While attempting any question always remember the following points:

o Where OR is used in the description of a language it means that expressions on both sides of ‘OR’ are parts of the language.

o Where NOT is used in the description of the language it means that language includes all strings except described in the ‘NOT’ condition, for example language NOT starting with a, means all strings not having a in the start (you have to evaluate yourself what kinds of strings are these).

Assignment Uploading Instructions:

o Upload single word file having solutions for all questions.

:::::::::::::::::::::::::::::::::::::::::::::::

Solution: