11-12-2011, 08:49 PM
Theory of Automata (CS402)
Assignment No.2
Assignment Submission Deadline
Your assignment must be uploaded before or on 17th of November, 2011. [Upload your assignment well before due date to avoid any assignment uploading related issues]
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
Objectives of this assignment are to make students able to understand the following concepts,
Transition graph (TG)
Generalized Transition graph (GTG)
NFA
Kleen’s Theorem
Question No.1
Draw the Transition graph (TG) for language of words in which the “b” occur only in even clumps and that end in four or more a’s.
Draw the Transition graph (TG) for language of words starting with three a’s or three b’s and ending with bb or aa
Draw the Transition graph (TG) for language of words having aab or bba anywhere in it
Draw the Transition Graph (TG) for language of words EVEN-EVEN,
Draw the Generalized Transition graph (GTG) for below given regular expression:
a*+ (ab+a)*(b+ Λ
+a*
Question No.2
Review the below given TG and check if the below given words can be read through this TG.
a
bba
bbab
abbaaabba
Question No.3
Consider the FA1 and FA2 given below,
FA1
FA2
Give RE’s corresponding to FA1 and FA2
Find FA and RE corresponding to the Union of FAs (FA1 + FA2)
Find FA and RE corresponding to Concatenation of FA’s (FA1.FA2)
Hint: First find FA and then find RE considering that FA as TG
Question No.4
Consider the FA1given below and find its closure (FA1*) also give RE before and after finding closure.
FA1
Question No.5
Give Non Deterministic Finite Automata (NFA) for each of the following language defined over alphabet Σ = {a, b}
Language having all strings with alternating a’s and b’s , some example strings are ababab… or bababa…
Language having all strings NOT containing aa at any place
Assignment No.2
Assignment Submission Deadline
Your assignment must be uploaded before or on 17th of November, 2011. [Upload your assignment well before due date to avoid any assignment uploading related issues]
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
Objectives of this assignment are to make students able to understand the following concepts,
Transition graph (TG)
Generalized Transition graph (GTG)
NFA
Kleen’s Theorem
Question No.1
Draw the Transition graph (TG) for language of words in which the “b” occur only in even clumps and that end in four or more a’s.
Draw the Transition graph (TG) for language of words starting with three a’s or three b’s and ending with bb or aa
Draw the Transition graph (TG) for language of words having aab or bba anywhere in it
Draw the Transition Graph (TG) for language of words EVEN-EVEN,
Draw the Generalized Transition graph (GTG) for below given regular expression:
a*+ (ab+a)*(b+ Λ
+a*Question No.2
Review the below given TG and check if the below given words can be read through this TG.
a
bba
bbab
abbaaabba
Question No.3
Consider the FA1 and FA2 given below,
FA1
FA2
Give RE’s corresponding to FA1 and FA2
Find FA and RE corresponding to the Union of FAs (FA1 + FA2)
Find FA and RE corresponding to Concatenation of FA’s (FA1.FA2)
Hint: First find FA and then find RE considering that FA as TG
Question No.4
Consider the FA1given below and find its closure (FA1*) also give RE before and after finding closure.
FA1
Question No.5
Give Non Deterministic Finite Automata (NFA) for each of the following language defined over alphabet Σ = {a, b}
Language having all strings with alternating a’s and b’s , some example strings are ababab… or bababa…
Language having all strings NOT containing aa at any place
0300-9520262
Get solution in 24 hour |cpmputer & internet
mileys81:[SIZE="4"][SIZE="3"]....[/SIZE][/SIZE]
