CS402 QUiZ 1 Fall 2024

 

 Click Here To Download

There _______ be dead states in NFA.

Select correct option:

may not

must

should not

will

 

1 Let FA1 accepts many strings and FA2 accepts none then FA1+FA2 will be equal to:

 Select correct option:

FA1

 FA2

 FA2-FA1

(FA2)*

 

If FA1 corresponds to (a+b)* then FA1 must accept ___________ string/strings.

 Select correct option:

No

Odd length

Even length

Every

 

The minimum length of the strings(except null string) of a language that starts and ends in the same letters will be:

Select correct option:

1

2

3

4

 

A regular language can be:

Select correct option:

irregular

infinite

non-deterministic

None of the given options

 

There ______ a language for which only FA can be built but not the RE.

Select correct option:

is cannot be

 may be

may not be

 

For every three regular expressions R, S, and T, the languages denoted by R(S U T) and (RS) U (RT) are the ______ .

 Select correct option:

Same

Different

 

In _______ there must be transition for all the lettersof a string.

 Select correct option:

 NFA

GTG

TG

FA

 

We cannot construct an NFA for the language of ______ defined over alphabet set {a,b}.

Select correct option:

Even

odd

Palindromes

Integers

 

Decomposing a string into its valid units is referred as:

Select correct option:

Decomposing

Splitting

Tokenizing

Dividing

 

 

In concatenation we accept the initial state of FA2 automatically after the final state of FA1 because of:

Select correct option:

We need just one initial state (correct)

 

Considering FA1 and FA2 having 2 states each. Now FA1+FA2 can have maximum ______________ number of states.

Select correct option:

2

3

more than 3

None of these

 

Let FA3 be an FA corresponding to FA1FA2, then the initial state of FA3 must correspond to the initial state of Select correct option:

FA1

only FA2

only FA1

 

Let FA1 accepts many strings and FA2 accepts none then FA1+FA2 will be equal to:

Select correct option:

FA1

FA2

FA2-FA1

(FA2)*

 

 

FA and _______ are same except that _______ has unique symbol for each transition.

Select correct option:

FA,TG

NFA,TG

NFA,FA

GTG,NFA

 

If R is a regular language and L is some language, and L U R is a _______, then L must be a ________.

Select correct option:

Regular language

Finite Aut

 

The minimum length of the strings(except null string) of a language that starts and ends in the same letters will be:

Select correct option:

1

2

3

4

 

For every three regular expressions R, S, and T, the languages denoted by R(S U T) and (RS) U (RT) are the ______ .

Select correct option:

Same

Differen

 

There _______ be dead states in NFA.

Select correct option:

may

not must

should not

will

 

In _______ there must be transition for all the lettersof a string.

Select correct option:

NFA

GTG

TG

FA

 

The minimum length of the strings(except null string) of a language that starts and ends in different letters will be:

Select correct option:

1

2

3

4

 

Consider we have languages L7 and L6. Which of the following represents their concatenation?

Select correct option:

·                  L7+L6

·                  L7/L6

·                  L6L7

·                  L7L6

 

In concatenation we accept the initial state of FA2 automatically after the final state of FA1 because of:

Select correct option:

We need just one init

 

There _______ be dead states in NFA.

Select correct option:

may

not must

should not

will

 

If we have a finite language and the number of states in the FA is n then the maximum number of letters in the each word of the language that will be ac

·                  1

·                  n-1

·                  n+1

·                  n

 

FA3 be an FA corresponding to FA1FA2, then the initial state of FA3 must correspond to the initial state of

Select correct option:

FA1 only

FA2 only

 

Consider we have languages L7 and L6. Which of the following represents their concatenation?

Select correct option:

L7+L6

L7/L6

L6L7

L7L6

 

Let FA1 has x number of states and FA2 has y number of states. Now FA1+FA2 can have maximum _______________ number of states. Select correct option:

·                  x+y

        x-y

·                  x/y

    none

 

The language {a ab aba bab} is _____ .

Select correct option:

Irregular

Regular

Recursive

None of the given options

 

The minimum length of the strings(except null string) of a language that starts and ends in the same letters will be:

Select correct option:

1

2

3

4

 

The minimum length of the strings(except null string) of a language that starts and ends in different letters will be:

Select correct option:

1

2

3

 

In _______ there must be transition for all the lettersof a string.

Select correct option:

NFA

GTG

TG

FA

Question No: 1 ( Marks: 1 ) – Please choose one
Σ={a,Aa,Abb}, then string aAaAbbAa has ________ length.
► One
► Two
► Three
► Four (Page 4)

Question No: 2 ( Marks: 1 ) – Please choose one
Languages generated by kleene star are always ______________.
► Finite
► Infinite (Page 7)
► Sometimes finite & sometimes infinite
► None of the these

Question No: 3 ( Marks: 1 ) – Please choose one
Let S = {aa, bb} be a set of strings then s* will have
► Λ (Page 7)
► abba
► aabbbaa
► bbaab

Question No: 4 ( Marks: 1 ) – Please choose one
If r1 = (aa + bb) and r2 = ( a + b) then the language (aa + bb)* will be generated by
► (r1)(r2)
► (r1 + r2)
► (r2)*
► (r1)* (Page 10)
2
Question No: 5 ( Marks: 1 ) – Please choose one
y
a, b

x ±
a, b
Above given FA can be represented by
► ((a+ b) (a + b))* (Page 13)
► (a + b)(a + b)*
► (a + b)(a + b)
► (a + b)*(a + b)*

Question No: 6 ( Marks: 1 ) – Please choose one
a,b
2+

1±
a,b
Above given FA accepts ___________ strings defined over Σ={a , b}
► All (Page 15)
► Some
► All but not null
► None of these

Question No: 7 ( Marks: 1 ) – Please choose one
If a language can be expressed through FA, then it can also be expressed through TG.
► True (Page 25)
► False
► Depends on language
► None of the above

Question No: 8 ( Marks: 1 ) – Please choose one
b
b

3+
a
1-
a
a
a
a

4+
b
2-
.b
b
a
b

5 6
Above given TG has ____________________ RE.
► a+b+a(a + b)*a + b(a + b)*b
► a(a + b)*a + b(a + b)*b
► both are given
► none of the given
3
Question No: 9 ( Marks: 1 ) – Please choose one
b
b

3+
a
1-
a
a
a
a

4+
b
2-
.b
b
a
b

5
6
Above given FA accepts the language in which strings
► Begins with and ends in same letter
► Begins with and ends in different letter
► Has length more than 2
► None of the given

Question No: 10 ( Marks: 1 ) – Please choose one
GTG can have _______________ final state.
► 0
► 1
► More than 1
► All of the given Click here for detail

Question No: 11 ( Marks: 1 ) – Please choose one
In GTG, if a state has more than one incoming transitions from a state. Then all those incoming transitions can
be reduced to one transition using _____________ sign
► –
► + (Page 27)
► *
► None of the given
Question No: 12 ( Marks: 1 ) – Please choose one
“One language can be expressed by more than one NFA”. This statement is ______________.
► False
► True (Page 41)
► Depends on NFA
► None of the given
4
Question No: 13 ( Marks: 1 ) – Please choose one

aa+bb
ab+ba
ab+ba
aa+bb

Λ
4+
3- 1 2
Λ
If above given TG is drawn like

aa+bb

Λ
4
+
3
–
1
Λ
X
Then what will be written in place of X.
► (ab+ba)(aa+bb)(ba+ab)
► (ab+ba)(aa+bb)(ab+ba)
► (ab+ba)(aa+bb)*(ab+ba) (Page 31)
► (ab+ba)(aa+bb)(ab+ba)*

Question No: 14 ( Marks: 1 ) – Please choose one

a

^
1-
4+
b
5
a
a
a
^, b
a
2
3
Above given structure is an ________.
► FA
► NFA
► NFA -^ (Page 42)
► TG
5
Question No: 15 ( Marks: 1 ) – Please choose one
One FA has 3 states and 2 letters in the alphabet. Then FA will have ___________ number of transitions in the
diagram
► 4
► 5
► 7
► 6 (Page 14)

Question No: 16 ( Marks: 1 ) – Please choose one
aa

b

bb

a

1-
2-
3+
4+
b
a
Above given two TG’s are _______________.
► Equivalent (Page 26 – 27)
► None-equivalent
► Not valid
► None of the given

MIDTERM EXAMINATION
Spring 2010
CS402- Theory of Automata
Question No: 1 ( Marks: 1 ) – Please choose one
If an alphabet has n number of letter, then number of strings of length m will be
►n+m
► (n)(m)
►m^n
►n^m (Page 6)
6
Question No: 2 ( Marks: 1 ) – Please choose one
Languages generated by kleene star are always ______________.
►Finite
►Infinite (Page 7) rep
►Sometimes finite & sometimes infinite
►None of the these
Question No: 3 ( Marks: 1 ) – Please choose one
►True
►False
►Sometimes true & sometimes false
►None of these
Question No: 4 ( Marks: 1 ) – Please choose one
a*b* = (ab)* this expression is __________
►True
►False
►Can’t be assumed
►None of these
Question No: 5 ( Marks: 1 ) – Please choose one
Above given FA can be expressed as ________
► (a + b)* (Page 19)
►a* + b*
► (ab + ba)*
►None of these
Question No: 6 ( Marks: 1 ) – Please choose one
If a language is expressed through TG, then that language will have its RE.
►True (Page 25)
►False
►Depends on language
►None of these
7
Question No: 7 ( Marks: 1 ) – Please choose one
Above given FA accepts _____________ language.
►Finite (Page 17)
►Infinite
►Depends on alphabet
►None of these
Question No: 8 ( Marks: 1 ) – Please choose one
In TG there may exist more than one path for certain string.
►True (Page 25)
►False
►Depends on the language
►None of these
Question No: 9 ( Marks: 1 ) – Please choose one
In TG there may exist no paths for certain string.
►True (Page 25)
►False
►Depends on the language
►None of these
8
Question No: 10 ( Marks: 1 ) – Please choose one
GTG can have _______________ final state.
►0
►1
►More than 1
►All of the given Click here for detail Rep
Question No: 11 ( Marks: 1 ) – Please choose one
Above given diagram is an NFA. If we convert it into an FA using transition table, then new FA will be
consisted on ______________ number of states.
►6
►5
►4 (Page 45)
►3
Question No: 12 ( Marks: 1 ) – Please choose one
Above given TG accepts the language in which all strings
►Ends in b
►Begins with b
►Ends and begins with b
►None of the given
Question No: 13 ( Marks: 1 ) – Please choose one
Above given TG has _____________ RE.
►a(a + b)*b + b(a + b)*a
►b(b + a)*a + b(a + b)*a
►None of these
►a(a + b)*a + b(a + b)*b
9
Question No: 14 ( Marks: 1 ) – Please choose one
Every FA should be __________
►Deterministic (Page 25)
►Non- Deterministic
►Deterministic & Non- Deterministic
►None of these
MIDTERM EXAMINATION
Fall 2010
CS402- Theory of Automata
Question No: 1 (Marks: 1) – Please choose one
Auto Meta mean
► Manual work
► Automatic work (Page 3)
Question No: 2 (Marks: 1) – Please choose one
S= {a,bc,cc} has the latters
► 1
► 2
► 3
► 4
Question No: 3 (Marks: 1) – Please choose one
S={a,bb,bab,baabb} set of strings then S* will not have
► baba
► baabbab
► bbaaabb
► bbbaabaabb
Question No: 4 (Marks: 1) – Please choose one
One language can represents more than one RE.
► True (Page 9)
► Falss
► Can’t be assumed
► Non of given10
Question No: 5 (Marks: 1) – Please choose one
Given GTG has RE
► (a+b)* (aa+bb)(a+b)* (Page 24)
► None of option
Question No: 6 (Marks: 1) – Please choose one
NFA accept ______String
► b
► babab
► baaab
► all (Page 43)
Question No:7 (Marks: 1) – Please choose one
NFA accept ______String
► bab
► a
► aba
► a & aba (Page 43)
Question No: 8 (Marks: 1) – Please choose one
TG has
► (a+b)*
► Λ+(a+b)*a (Page 20)
► Λ+(a+b)*a*
► None of given
11
Question No: 9 (Marks: 1) – Please choose one
TG can more then one initial state
► True (Page 26)
► False
► Depend on alphabets
► None of given
Question No:10 (Marks: 1) – Please choose one

RE will be
► (a+b)*
► (a+b)*(a*+b*)
► None of the given (Page 37)
Ref:- regular expression corresponding to above two FA’s can be (a+b)((a+b)(a+b))* or ((a+b)(a+b))*(a+b)
Question No: 11 (Marks: 1) – Please choose one
The clouser FA*(star on an FA ) always accept ______string
► Null (Page 7)
► aa
► bb
► None of given
Question No: 12 (Marks: 1) – Please choose one
In FA final state represent by _________sign
► +
► –
► =
► *
Question No: 13 (Marks: 1) – Please choose one
In FA one enter in specific stat but there is no way to leave it then state is called
► Dead States
► Waste Baskets
► Davey John Lockers
► All of above (Page 17)
12
Question No: 14 (Marks: 1) – Please choose one
Using tree structure final state represent by
► *
► –
► double circle (Page 13)
► None of given
Question No: 15 (Marks: 1) – Please choose one
► a’s occur only in even clumps and that ends in three or more b’s (Page 22)
► length larger then 2
► it does not accept any language
► none of given option
Question No: 16 (Marks: 1) – Please choose one

These GTG are ________
► Equal (Page 27)
► Not equal
► Not valid
► None of given
Question No: 17 (Marks: 1) – Please choose one

NFA to FA will_____________
► Equal (Page 43)
► Not equal
► Not valid
► None of given
13
Question No: 18 (Marks: 1) – Please choose one
FA having RE______
Λ + a + b + (a+b)*(ab+ba+bb) (Page 18)
a + b + (a+b)*(ab+ba+bb).
MIDTERM EXAMINATION
Fall 2010
CS402- Theory of Automata
Question No: 1 (Marks: 1) – Please choose one
Length of strings, generated by infinite language is_______
►finite (Page 7)
►infinite
►none of these
Ref:- By infinite language, it is supposed that the language contains infinite many words, each of finite length
Question No: 2 (Marks: 1) – Please choose one
RE for the language defined over Σ={a,b} having words starting with a is____
►a(a+b)* (Page 12)
► (a+b)*a
► (a+b)*
►None of these
14
Question No: 3 (Marks: 1) – Please choose one
“Every Infinite language is regular” this statement is
►True (Page 11)
►False
Question No: 4 (Marks: 1) – Please choose one
2+
a,b

1 –
a,b
Above given FA accepts the null string
►True
►False
Question No: 5 (Marks: 1) – Please choose one
aa+bb
a+b a+b
– +
Above given GTG accepts the language in which strings
Contains double a or double b (Page 24)
Contains both a and double b
Depends on the alphabet
None of these
Question No: 6 (Marks: 1) – Please choose one

b

a
1-

a
a
5+
2+
3
4
Above given NFA accepts the ______ number of strings
►one
►two (Page 40)
►three
►four
15
Question No: 7 (Marks: 1) – Please choose one

aa+bb
ab+ba
ab+ba
aa+bb

Λ
4+
3- 1 2
Λ
If above given TG is drawn like

aa+bb

Λ
4
+
3
–
1
Λ
X
Then what will be written in place of X.
► (ab+ba)(aa+bb)(ba+ab)
► (ab+ba)(aa+bb)(ab+ba)
► (ab+ba)(aa+bb)*(ab+ba) (Page 31) rep
► (ab+ba)(aa+bb)(ab+ba)*
Question No: 8 (Marks: 1) – Please choose one

a

^
1-
4+
b
5
a
a
a
^, b
a
2
3
Above given structure is an ________.
► FA
► NFA
► NFA -^ (Page 42) rep
► TG
16
Question No: 9 (Marks: 1) – Please choose one
TG is always deterministic.
►True
►False (Page 25)
Question No: 10 (Marks: 1) – Please choose one
The length of output string in case of _________ is one more than the length of corresponding input string.
►Finite Automaton (Page 55)
►TG
►GTG
Question No: 11 (Marks: 1) – Please choose one
b

––

+
a,b
Above given TG accepts the _____________ string.
►bb
►baba
►bbba
►all of the given options (Page 19)
Question No: 12 (Marks: 1) – Please choose one
If in an NFA,
Ù
is allowed to be a label of an edge then that NFA is called _________.
Will not remain NFA
NFA with
NFA with null string (Page 42) rep
Either “NFA with null string” OR “NFA with ”
Question No: 13 (Marks: 1) – Please choose one
Above given FA generates the strings which __________
►Starting and ending with same letters
► Starting and ending with different letters
►None of these
17
Question No: 14 (Marks: 1) – Please choose one
Above given FA accepts _____________ language.
►Finite (Page 17) rep
►Infinite
►Depends on alphabet
►None of these
MIDTERM EXAMINATION
Spring 2009
CS402- Theory of Automata (Session – 3)
Question No: 1 ( Marks: 1 ) – Please choose one
Length of null string is
►Always not equal to 0
►Always equal to 0 click here for detail
►It has variable length
►All are true
18
Question No: 2 ( Marks: 1 ) – Please choose one
If an alphabet has n number of letter, then number of strings of length m will be
►n+m
► (n)(m)
►m^n
►n^m (Page 6) rep
Question No: 3 ( Marks: 1 ) – Please choose one
Languages generated by kleene star are always ______________.
►Finite
►Infinite (Page 7) rep
►Sometimes finite & sometimes infinite
►None of the these
Question No: 4 ( Marks: 1 ) – Please choose one
“Every finite language can be expressed by FA”. This statement is __________.
►True
►False
►Depends on language
►None of these
Question No: 5 ( Marks: 1 ) – Please choose one
In FA, if one enters in a specific state but there is no way to leave it, then that specific state is called
►Dead States
►Waste Baskets
►Davey John Lockers
►All of these (Page 17)
Question No: 6 ( Marks: 1 ) – Please choose one
In TG there may exist no paths for certain string.
►True (Page 25) rep
►False
►Depends on the language
►None of these
Question No: 7 ( Marks: 1 ) – Please choose one
In GTG’s there may exist no path for a certain string.
►True (Page 25)
►False
►Depends on alphabet
►None of these
19
Question No: 8 ( Marks: 1 ) – Please choose one
In drawing FA3 (which is equal to FA1 + FA2), a state will be declared final if
►States of both FA’s are final
►At least one state is final (Page 32)
►Depends on language
►None of the given
Ref:- Let FA3 be an FA corresponding to r1r2, then the initial state of FA3 must correspond to the initial state
of FA1 and the final state of FA3 must correspond to the final state of FA2.
Question No: 9 ( Marks: 1 ) – Please choose one
Above given structure is an ________.
►FA
►NFA
►NFA -^ (Page 42) rep
►TG
Question No: 10 ( Marks: 1 ) – Please choose one
►Above given TG represents the language____
►Begins and ends with same letters
►Begins and ends with different letters (Page 21)
►Begins with a
►None of these
20
Question No: 11 ( Marks: 1 ) – Please choose one
In TG, there may be a transition for null string.
►True (Page 18)
►False
►Can’t show transition for string
►None of these
Ref:- Finite set of transitions that show how to go from one state to another based on reading specified
substrings of input letters, possibly even the null string (Λ).
Question No: 12 ( Marks: 1 ) – Please choose one
The _______ machine helps in building a machine that can perform the addition of binary numbers.
►Incrementing (Page 60)
►Complementing
►Decrementing
►None of the given
Question No: 13 ( Marks: 1 ) – Please choose one
►GTG can have _____________ initial state.
►Zero
►One
►More than One
►One OR more than One (Page 23)
Ref:- Finite number of states, at least one of which is start state and some (maybe none) final states.
Question No: 14 ( Marks: 1 ) – Please choose one
One FA has n states and m letters in the alphabet. Then FA will have _____ number of transitions in the
diagram.
► (n)+(m)
► (m)(n) OR (n)(m)
►None of the given options
► (m)-(n)
Question No: 15 ( Marks: 1 ) – Please choose one
If L1 and L2 are expressed by regular expressions r1 and r2, respectively then the language expressed by r1 +
r2 will be _________
►Regular (Page 10)
►Ir-regular
►Can’t be decided
►Another Language which is not listed here21
Question No: 16 ( Marks: 1 ) – Please choose one
Which statement is true?
►All words are strings (Page 3)
►All strings are words
►Both are always same
►None of these
MIDTERM EXAMINATION
Spring 2009
CS402- Theory of Automata (Session – 3)
Question No: 1 ( Marks: 1 ) – Please choose one
Alphabet S = {a,bc,cc} has _______ number of letters.
►One
►Two
►Three rep
►Four
Question No: 2 ( Marks: 1 ) – Please choose one
One language can be represented by more than one RE” this statement is____
►False
►True (Page 9)
►Can’t be assumed
►None of these
Question No: 3 ( Marks: 1 ) – Please choose one
(a + b)*b is RE for the language defined over S={a,b} having words not ending in a
►True (Page 13)
►False
►Such a language is not regular
►None of these22
Question No: 4 ( Marks: 1 ) – Please choose one
Above given FA accepts ___________ strings defined over S={a , b}
►All (Page 15) rep
►Some
►All but not null
►None of these
Question No: 5 ( Marks: 1 ) – Please choose one
Above given GTG accepts the language in which strings
►Begins and ends with different letters (Page 24)
►Begins and ends with same letters
►Have length greater than 1
►None of these
Question No: 6 ( Marks: 1 ) – Please choose one
According to 3rd part of the Kleene’s theorem, If a language can be accepted by an RE then it can be accepted
by a _________ as well
►TG
►FA
►G and FA (Page 25)
►None of these
Question No: 7 ( Marks: 1 ) – Please choose one
If FA1 accepts no string and FA2 accepts many strings, then FA1 + FA2 will be equal to
►FA1
►FA2
►May be both
►None of the given
23
Question No: 8 ( Marks: 1 ) – Please choose one
Above given GTG’s are ______________
►Equivalent (Page 27) rep
►Non-equivalent
►Non-valid
►None of the given
Question No: 9 ( Marks: 1 ) – Please choose one
Above given NFA and FA generate same language.
►True (Page 41)
►False
►FA & NFA can’t be equivalent
►None of these
Question No: 10 ( Marks: 1 ) – Please choose one
Above given structure is a ______________
►FA
►TG
►NFA (Page 44)
►FA and NFA
24
Question No: 11 ( Marks: 1 ) – Please choose one
Above given TG has the ______________ RE.
► (a + b)*a
►λ+ (a + b)*a (Page 20)
►None of these
►λ + (a + b)*a*
Question No: 12 ( Marks: 1 ) – Please choose one
Above given TG’s are ______________.
►Equivalent (Page 21)
►Non-equivalent
►TG’s are not valid
►None of these
Question No: 13 ( Marks: 1 ) – Please choose one25
Above given FA has _________ RE.
► (a + b)*a (Page 13)
► a(a + b)*
► ((a + b)*a)*
► (a + b)*a & ((a + b)*a)*
Question No: 14 ( Marks: 1 ) – Please choose one
Above given TG accepts the _____________ string.
►bb
►baba
►bbba
►all of the given options (Page 19) rep
Question No: 15 ( Marks: 1 ) – Please choose one
Above given FA and NFA are equivalent. This statement is ______________.
►True (Page 43) rep
►False
►FA & NFA can never be equivalent
►None of the given options
26
MIDTERM EXAMINATION
Spring 2009
CS402- Theory of Automata (Session – 3)
Question No: 1 ( Marks: 1 ) – Please choose one
If r1 and r2 are regular expressions then which of the following is not regular expression.
►r1 = r2
►r1r2
►r1*
►r1 – r2 (Page 9)
Question No: 2 ( Marks: 1 ) – Please choose one
Which of the following is not a word of language EQUAL?
►aaabbb
►abbbabaa
►abababa (Page 5)
►bbbaaa
Question No: 3 ( Marks: 1 ) – Please choose one
If S = {aa, bb}, then S* will not contain..
►aabbaa
►bbaabbbb
►aaabbb
►aabbbb
Question No: 4 ( Marks: 1 ) – Please choose one
One language can be represented by more than one RE” this statement is____
►False
►True (Page 9) rep
►Can’t be assumed
►None of these
Question No: 5 ( Marks: 1 ) – Please choose one
“Every Infinite language is regular” this statement is
►True (Page 11) rep
►False
►Can’t be supposed
►None of these
27
Question No: 6 ( Marks: 1 ) – Please choose one
PALINDROME can be defined by more than one regular language
►True
►False (Page 71)
►By only one RE
►Some times By only one RE and Some times False
Question No: 7 ( Marks: 1 ) – Please choose one
Above given FA can be expressed as ________
► (a + b)* (Page 19) rep
►a* + b*
► (ab + ba)*
►None of these
Question No: 8 ( Marks: 1 ) – Please choose one
Above given FA is drawn using
►Tree structure (Page 18)
►It is not an FA
►Graph structure
►None of these
28
Question No: 9 ( Marks: 1 ) – Please choose one
Above given GTG accepts the language in which strings
►Contains double a or double b (Page 24) rep
►Contains both a and double b
►Depends on the alphabet
►None of these
Question No: 10 ( Marks: 1 ) – Please choose one

aa+bb
ab+ba
ab+ba
aa+bb

Λ
4+
3- 1 2
Λ
If above given TG is drawn like

aa+bb

Λ
4
+
3
–
1
Λ
X
Then what will be written in place of X.
► (ab+ba)(aa+bb)(ba+ab)
► (ab+ba)(aa+bb)(ab+ba)
► (ab+ba)(aa+bb)*(ab+ba) (Page 31) rep
► (ab+ba)(aa+bb)(ab+ba)*
29
Question No: 11 ( Marks: 1 ) – Please choose one
Above given NFA-^ accepts____
►bab
►a
►aba
►a & aba rep
Question No: 12 ( Marks: 1 ) – Please choose one
Above given structure is a _________________.
►FA
►TG
►FA & TG
►NFA (Page 44)
Question No: 13 ( Marks: 1 ) – Please choose one
Above given TG has _____________ RE.
► (aa+aa+(ab+ab)(aa+ab)*(ab+ba))*
► (aa+bb+(ab+ba)(aa+bb)*(ab+ba))* (Page 22)
► (aa+bb+(ab+ba)(aa+bb)(ab+ba))*
►None of these
Question No: 14 ( Marks: 1 ) – Please choose one
Above given TG has _______________ RE.
►b(a + b)* (Page 19)
►b*(a + b)*
►b*(a + b)
►None of these
30
Question No: 15 ( Marks: 1 ) – Please choose one
Above given two TG’s are _______________.
►Equivalent (Page 26 – 27) rep
►None-equivalent
►Not valid
►None of the given
Question No: 16 ( Marks: 1 ) – Please choose one
Above given TG has __________________________ RE.
► (aa+bb+(ab+ba)(aa+bb)(ab+ba))*
► (aa+bb+(ab+ba)(aa+bb)*(ab+ba))* (Page 22) rep
► (aa+ba+(bb+ba)(ab+bb)(ab+aa))*
► (ab+ba+(ab+ba)(aa+bb)(ab+ba))*
31
MIDTERM EXAMINATION
Spring 2009
CS402- Theory of Automata (Session – 3)
Question No: 1 ( Marks: 1 ) – Please choose one
S = {baa, ab}, then S* will not contain
►abbaab
►abab
►baabaa
►abbaa
Question No: 2 ( Marks: 1 ) – Please choose one
►True rep
►False
►Sometimes true & sometimes false
►None of these
Question No: 3 ( Marks: 1 ) – Please choose one
One language can be represented by more than one RE” this statement is____
►False
►True (Page 9) rep
►Can’t be assumed
►None of these
Question No: 4 ( Marks: 1 ) – Please choose one
a(a+b)*a+b(a+b)*b is RE for the language defined over S={a,b} having words beginning and ending with same
letters
►True (Page 14)
►False
►Such a language is not regular
►None of these
Question No: 5 ( Marks: 1 ) – Please choose one
If a language has RE, then that language can be expressed through TG.
►True (Page 25) rep
►False
►Depends on language
►None of these
32
Question No: 6 ( Marks: 1 ) – Please choose one
Above given FA can be expressed by
► (a + b)*a (Page 14)
► (a + b)*b
►a (a + b)*
►b (a + b)*
Question No: 7 ( Marks: 1 ) Please choose one
In TG there may exist no paths for certain string.
►True (Page 25) rep
►False
►Depends on the language
►None of these
Question No: 8 ( Marks: 1 ) – Please choose one
FA3 will express r1r2. then F3 will have ____________________ number of states in its diagram.
►8
►7
►6 (Page 36)
►5
Question No: 9 ( Marks: 1 ) – Please choose one
FA1 corresponds to r*, then FA1 must accept _______________ string.
►Every (Page 07)
►Null
►Odd length
►Even length
33
Question No: 10 ( Marks: 1 ) – Please choose one
In NFA, there may be more than one transition for certain letters and there may not be any transition for certain
letters. This statement is ______________.
►False
►True (Page 40)
►Depends on language
►None of the given
Question No: 11 ( Marks: 1 ) – Please choose one
Above given TG accepts the language in which all strings
►Ends in b
►Begins with b (Page 19)
►Ends and begins with b
►None of the given
Question No: 12 ( Marks: 1 ) – Please choose one
Above given TG represents the language____
►Begins and ends with same letters
►Begins and ends with different letters (Page 21) rep
►Begins with a
►None of these
34
Question No: 13 ( Marks: 1 ) – Please choose one
Above given TG represents the language i.e.
►EVEN-EVEN (Page 22)
►PALINDROME
►FACTORIAL
►None of these
Question No: 14 ( Marks: 1 ) – Please choose one
FA1 and FA2 are two FA’s representing two languages. Then FA3, which is sum of FA1 and FA2, will accept
the strings which are
►Accepted by FA1 AND FA2
►Accepted by FA1 OR FA2
►Accepted by FA1 AND/OR FA2 (Page 32)
►None of the given options
Ref:- language corresponding to r1+ r2 is the union of corresponding languages L1 and L2, consists of the
strings belonging to L1or L2 or both
Question No: 15 ( Marks: 1 ) – Please choose one
a (a + b)* is the RE of language defined over S = {a, b} having at least one a
►True
►False
►Such a language does not exist
►None of the given options
Question No: 16 ( Marks: 1 ) – Please choose one
(a + b)* a is RE for the language defined over S={a,b} having words not ending in b
►True
►False
►Such a language is not regular
►None of the given options
35
MIDTERM EXAMINATION
Spring 2009
CS402- Theory of Automata (Session – 1)
Question No: 1 ( Marks: 1 ) – Please choose one
Alphabet S = {a,bc,cc} has _______ number of letters.
►One
►Two
►Three rep
►Four
Question No: 2 ( Marks: 1 ) – Please choose one
In which of the following language Rev(s)=s
►EQUAL
►INTEGER
►PALINDROME (Page 6)
►FACTORIAL
Question No: 3 ( Marks: 1 ) – Please choose one
If S = {ab, bb}, then S* will not contain
►abbbab
►bbba
►bbbbab
►ababbb
Question No: 4 ( Marks: 1 ) – Please choose one
Above given FA generates the language having strings of _________
►ODD length
►EVEN length
►Equal number of a’s and b’s
►None of these
36
Question No: 5 ( Marks: 1 ) – Please choose one
Above given GTG accepts the language in which strings
►Contains double a or double b (Page 24) rep
►Contains both a and double b
►Depends on the alphabet
►None of these
Question No: 6 ( Marks: 1 ) – Please choose one

aa+bb
ab+ba
ab+ba
aa+bb

Λ
4+
3- 1 2
Λ
If above given TG is drawn like

aa+bb

Λ
4
+
3
–
1
Λ
X
Then what will be written in place of X.
► (ab+ba)(aa+bb)(ba+ab)
► (ab+ba)(aa+bb)(ab+ba)
► (ab+ba)(aa+bb)*(ab+ba) (Page 31) rep
► (ab+ba)(aa+bb)(ab+ba)*
Question No: 7 ( Marks: 1 ) – Please choose one
FA3 expresses r1r2. Then initial state of FA3 will consist of
►Initial state of FA2
►Initial state of FA1 (Page 35)
►Initial states of both FA1 & FA2
►Depends on FA’s
37
Question No: 8 ( Marks: 1 ) – Please choose one
FA3 expresses r1r2. Then there will be at least one final state of FA3 that consist of final state of FA1 and
initial state of FA2.
►True
►False (Page 35)
►Depends on language
►None of these
Question No: 9 ( Marks: 1 ) – Please choose one
Two machines are said to be equivalent if they print the same output string when the different input string is run
on them
►True
►False (Page 60)
►Depends on language
►May be or may not be
Question No: 10 ( Marks: 1 ) – Please choose one
Running the string abbabbba on this Moore machine. The outputs will be________
►101111010 (Page 62)
►01111010
►01011110
►01010101
38
Question No: 11 ( Marks: 1 ) – Please choose one
Above given TG’s are ______________.
►None of these
►Equivalent (Page 21) rep
►Non-equivalent
►TG’s are not valid
Question No: 12 ( Marks: 1 ) – Please choose one
TG can have more than one initial state.
►True (Page 18)
►False
►Depends on alphabets
►None of these
Question No: 13 ( Marks: 1 ) – Please choose one
Above given FA accepts null string.
►True
►False
►FA is not valid
►None of these
39
Question No: 14 ( Marks: 1 ) – Please choose one
If in an NFA,
Ù
is allowed to be a label of an edge then that NFA is called _________.
►Will not remain NFA
►NFA with
►NFA with null string (Page 42) rep
►Either “NFA with null string” OR “NFA with ”
Question No: 15 ( Marks: 1 ) – Please choose one
One FA has n states and m letters in the alphabet. Then FA will have _____ number of transitions in the
diagram.
► (n)+(m)
► (m)(n) OR (n)(m) rep
►None of the given options
► (m)-(n)
Question No: 16 ( Marks: 1 ) – Please choose one
(a+b)*a(a+b)*b(a+b)* is the RE of language defined over S={a,b} having at least one a
and one b
►True
►False
►Such a language does not exist
►None of the given options