CS402 Theory of Automata Assignment No.2 april 2011

[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