CS402 Theory of Automata Assignment No.2 april 2011

[Vuhelper]

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
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

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.
b b
b

[moon13]

please do somthing quickly

[Vuhelper]

oky workinggg

[moon13]

only few hours left so please work quickly please

[Xpert]

ok dear.. i will send solution in pm only.

[moon13]

please explain pm mean

[Xpert]

Dear download it from this link.... Cs402 spring 2011 solution

[gm mughal]

Xpert yar kia haall hain Theory of automata ki 2nd assignment ka solution to send krna yar

[Xpert]

uper link dia howa hai click on it. then you can get the file.

[amirfreed]

These are the question and u did not give answer any one of them
[FONT=&quot][/FONT]

[FONT=&quot]Question No.1[/FONT]

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.
   
2. Draw the Transition graph (TG) for language of words starting with three a’s or three b’s and ending with bb or aa
   
3. Draw the Transition graph (TG) for language of words having aab or bba anywhere in it
   
4. Draw the Transition Graph (TG) for language of words EVEN-EVEN,
   
5. Draw the Generalized Transition graph (GTG) for below given regular expression:
   

[FONT=&quot]a*+ (ab+a)*(b+[/FONT][FONT=&quot] [/FONT][FONT=&quot]Λ[/FONT][FONT=&quot])+a*[/FONT]

[FONT=&quot]Question No.2 [/FONT]

Review the below given TG and check if the below given words can be read through this TG.

1. a
   
2. bba
   
3. bbab
   
4. abbaaabba
   

[IMG]file:///C:/DOCUME%7E1/ADMINI%7E1/LOCALS%7E1/Temp/msohtml1/01/clip_image002.gif[/IMG]

[FONT=&quot]Question No.3[/FONT]

[FONT=&quot]Consider the FA1 and FA2 given below, [/FONT]

FA1

[IMG]file:///C:/DOCUME%7E1/ADMINI%7E1/LOCALS%7E1/Temp/msohtml1/01/clip_image003.gif[/IMG]

FA2

[IMG]file:///C:/DOCUME%7E1/ADMINI%7E1/LOCALS%7E1/Temp/msohtml1/01/clip_image004.gif[/IMG]

1. Give RE’s corresponding to FA1 and FA2
   
2. Find FA and RE corresponding to the Union of FAs (FA1 + FA2)
   
3. 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

[FONT=&quot]Question No.4[/FONT]

[FONT=&quot]Consider the FA1given below and find its closure (FA1*) also give RE before and after finding closure.[/FONT]

FA1

[IMG]file:///C:/DOCUME%7E1/ADMINI%7E1/LOCALS%7E1/Temp/msohtml1/01/clip_image005.gif[/IMG]

[FONT=&quot]Question No.5[/FONT]

Give Non Deterministic Finite Automata (NFA) for each of the following language defined over alphabet Σ = {a, b}

1. Language having all strings with alternating a’s and b’s , some example strings are ababab… or bababa…
   
2. Language having all strings NOT containing aa at any place