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:
