Theory of Automata (CS402)View more random threads:
- cs604 Solution for the assignment no 2 fall 2010
- MGT201 Financial Management Spring 2011 GDB 1 Idea Solution...
- mth202 assignment no 5 solution fall 2011 on 24-01-2011
- CS506 assignment no 5 fall 2010 solution 29-01-2011
- CS408 Human Computer Interaction Assignment No. 02 Semester...
- cs201 assignmentno 5 solution fall 2010 on 27/01/2011
- CS101 Assignment#4( help required plz)
- CS604 Operating Systems vu current Assignment No 5 Spring...
- CS401 Computer Architecture and Assembly Language...
- CS501 ASSIGNMENT NO 1 fall 2011 solution on 29th October,...
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
And Let r2 = (a+b)* (bb) (a+b)* and the corresponding FA2 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...gnment1.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.
Sponsored Links
There are currently 1 users browsing this thread. (0 members and 1 guests)