Paper Tayyari

Midterm PreparationMidterm ki tayyari

Syllabus: lectures 1–24. Past-paper MCQs are shown first.Syllabus: lecture 1–24. Past paper ki MCQs pehle dikhai gayi hain.

55 MCQs · 45 short · 9 long questions · 55 MCQs from past papers55 MCQs · 45 short · 9 long sawal · 55 MCQs past papers se

Start mock testMock test shuru karein
DoneHal kiye 0/55
– correctsahi
1.
★ Midterm Spring 2010Lecture 1

Σ={a,Aa,Abb}, then string aAaAbbAa has ________ length.

  1. AOne
  2. BTwo
  3. CThree
  4. DFour

The string tokenizes as a, Aa, Abb, Aa, which is four letters.

2.
★ Midterm Spring 2010Lecture 1

If an alphabet has n number of letter, then number of strings of length m will be

  1. An+m
  2. B(n)(m)
  3. Cm^n
  4. Dn^m

Each of the m positions has n choices, giving n^m strings.

3.
★ Midterm Fall 2010Lecture 1

Auto Meta mean

  1. AManual work
  2. BAutomatic work

Automata comes from a word meaning self-acting or automatic.

4.
★ Midterm Fall 2010Lecture 1

Σ = {a,bc,cc} has the letters

  1. A1
  2. B2
  3. C3
  4. D4

The alphabet lists three letters: a, bc and cc.

5.
★ Midterm Fall 2010Lecture 1

Length of strings, generated by infinite language is_______

  1. Afinite
  2. Binfinite
  3. Cnone of these

An infinite language has infinitely many words, but each word has finite length.

6.
★ Midterm Spring 2009Lecture 1

Length of null string is

  1. AAlways not equal to 0
  2. BAlways equal to 0
  3. CIt has variable length
  4. DAll are true

The null string Λ has no letters, so its length is 0.

7.
★ Midterm Spring 2009Lecture 1

Which statement is true?

  1. AAll words are strings
  2. BAll strings are words
  3. CBoth are always same
  4. DNone of these

Words are strings that belong to a language, so every word is a string but not the reverse.

8.
★ Midterm Spring 2009Lecture 1

Which of the following is not a word of language EQUAL?

  1. Aaaabbb
  2. Babbbabaa
  3. Cabababa
  4. Dbbbaaa

abababa has four a's and three b's, so it is not in EQUAL.

9.
★ Midterm Spring 2009Lecture 1

In which of the following language Rev(s)=s

  1. AEQUAL
  2. BINTEGER
  3. CPALINDROME
  4. DFACTORIAL

PALINDROME is the language of words equal to their own reverse.

10.
★ Midterm Spring 2010Lecture 2

Languages generated by kleene star are always ______________.

  1. AFinite
  2. BInfinite
  3. CSometimes finite & sometimes infinite
  4. DNone of the these

As taught, the closure of a set with a non-null string contains infinitely many strings.

11.
★ Midterm Spring 2010Lecture 2

Let S = {aa, bb} be a set of strings then s* will have

  1. AΛ
  2. Babba
  3. Caabbbaa
  4. Dbbaab

S* always contains Λ, and the other strings cannot be split into aa and bb.

12.
★ Midterm Spring 2009Lecture 2

If S = {aa, bb}, then S* will not contain..

  1. Aaabbaa
  2. Bbbaabbbb
  3. Caaabbb
  4. Daabbbb

aaabbb has an odd run of a's, so it cannot be built from aa and bb.

13.
★ Midterm Spring 2009Lecture 2

S = {baa, ab}, then S* will not contain

  1. Aabbaab
  2. Babab
  3. Cbaabaa
  4. Dabbaa

abbaab splits as ab, baa and a leftover b, so it is not in S*; the others can be split.

14.
★ Midterm Spring 2010Lecture 3

If r1 = (aa + bb) and r2 = ( a + b) then the language (aa + bb)* will be generated by

  1. A(r1)(r2)
  2. B(r1 + r2)
  3. C(r2)*
  4. D(r1)*

(aa + bb)* is the Kleene star of r1.

15.
★ Midterm Fall 2010Lecture 3

RE for the language defined over Σ={a,b} having words starting with a is____

  1. Aa(a+b)*
  2. B(a+b)*a
  3. C(a+b)*
  4. DNone of these

The word must begin with a, followed by any string.

16.
★ Midterm Spring 2009Lecture 3

a (a + b)* is the RE of language defined over Σ = {a, b} having at least one a

  1. ATrue
  2. BFalse
  3. CSuch a language does not exist
  4. DNone of the given options

a(a+b)* only gives words starting with a; ba has an a but is missing.

17.
★ Midterm Spring 2009Lecture 3

(a+b)*a(a+b)*b(a+b)* is the RE of language defined over Σ={a,b} having at least one a and one b

  1. ATrue
  2. BFalse
  3. CSuch a language does not exist
  4. DNone of the given options

This RE needs an a before a b, so words like ba are missing.

18.
★ Midterm Spring 2010Lecture 4

a*b* = (ab)* this expression is __________

  1. ATrue
  2. BFalse
  3. CCan't be assumed
  4. DNone of these

aab is in a*b* but not in (ab)*, so they differ.

19.
★ Midterm Spring 2010Lecture 5

One FA has 3 states and 2 letters in the alphabet. Then FA will have ___________ number of transitions in the diagram

  1. A4
  2. B5
  3. C7
  4. D6

Each of the 3 states needs one transition for each of the 2 letters: 3 × 2 = 6.

20.
★ Midterm Spring 2010Lecture 5

Every FA should be __________

  1. ADeterministic
  2. BNon- Deterministic
  3. CDeterministic & Non- Deterministic
  4. DNone of these

An FA has exactly one transition per letter from each state.

21.
★ Midterm Fall 2010Lecture 5

In FA final state represent by _________sign

  1. A+
  2. B-
  3. C=
  4. D*

Final states are marked + and the initial state -.

22.
★ Midterm Spring 2009Lecture 5

One FA has n states and m letters in the alphabet. Then FA will have _____ number of transitions in the diagram.

  1. A(n)+(m)
  2. B(m)(n) OR (n)(m)
  3. CNone of the given options
  4. D(m)-(n)

Each of the n states has one transition for each of the m letters.

23.
★ Midterm Spring 2009Lecture 7

"Every finite language can be expressed by FA". This statement is __________.

  1. ATrue
  2. BFalse
  3. CDepends on language
  4. DNone of these

Every finite language is regular, so an FA can be built for it.

24.
★ Midterm Spring 2010Lecture 8

In TG there may exist more than one path for certain string.

  1. ATrue
  2. BFalse
  3. CDepends on the language
  4. DNone of these

A TG may be nondeterministic, so a string can have several paths.

25.
★ Midterm Spring 2010Lecture 8

In TG there may exist no paths for certain string.

  1. ATrue
  2. BFalse
  3. CDepends on the language
  4. DNone of these

A TG need not have an edge for every letter, so some strings have no path.

26.
★ Midterm Fall 2010Lecture 8

TG can more then one initial state

  1. ATrue
  2. BFalse
  3. CDepend on alphabets
  4. DNone of given

A TG may have several start states.

27.
★ Midterm Fall 2010Lecture 8

TG is always deterministic.

  1. ATrue
  2. BFalse

A TG may have several or no paths for a string, so it can be nondeterministic.

28.
★ Midterm Spring 2009Lecture 8

In TG, there may be a transition for null string.

  1. ATrue
  2. BFalse
  3. CCan't show transition for string
  4. DNone of these

TG edges may be labelled with Λ.

29.
★ Midterm Spring 2009Lecture 8

TG can have more than one initial state.

  1. ATrue
  2. BFalse
  3. CDepends on alphabets
  4. DNone of these

A TG may have several start states.

30.
★ Midterm Spring 2010Lecture 9

GTG can have _______________ final state.

  1. A0
  2. B1
  3. CMore than 1
  4. DAll of the given

A GTG may have no final state, one, or several.

31.
★ Midterm Spring 2010Lecture 9

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

  1. A-
  2. B+
  3. C*
  4. DNone of the given

Parallel edges labelled r1 and r2 become one edge labelled r1 + r2.

32.
★ Midterm Spring 2009Lecture 9

In GTG's there may exist no path for a certain string.

  1. ATrue
  2. BFalse
  3. CDepends on alphabet
  4. DNone of these

Like a TG, a GTG need not have a path for every string.

33.
★ Midterm Spring 2009Lecture 9

GTG can have _____________ initial state.

  1. AZero
  2. BOne
  3. CMore than One
  4. DOne OR more than One

A GTG has at least one start state and may have several.

34.
★ Midterm Spring 2009Lecture 15

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

  1. AFalse
  2. BTrue
  3. CDepends on language
  4. DNone of the given

This freedom is what makes an NFA nondeterministic.

35.
★ Midterm Fall 2010Lecture 16

If in an NFA, Λ is allowed to be a label of an edge then that NFA is called ________.

  1. AWill not remain NFA
  2. BNFA with Λ
  3. CNFA with null string
  4. DEither "NFA with null string" OR "NFA with Λ"

Such a machine is called both NFA with null string and NFA with Λ.

36.
★ Midterm Spring 2009Lecture 22

Two machines are said to be equivalent if they print the same output string when the different input string is run on them

  1. ATrue
  2. BFalse
  3. CDepends on language
  4. DMay be or may not be

Machines are equivalent when they print the same output for the same input string.

37.
★ Midterm Spring 2010

If a language can be expressed through FA, then it can also be expressed through TG.

  1. ATrue
  2. BFalse
  3. CDepends on language
  4. DNone of the above

Every FA is also a TG (Kleene's theorem part I).

38.
★ Midterm Spring 2010

"One language can be expressed by more than one NFA". This statement is ______________.

  1. AFalse
  2. BTrue
  3. CDepends on NFA
  4. DNone of the given

Many different NFAs can accept the same language.

39.
★ Midterm Spring 2010

If a language is expressed through TG, then that language will have its RE.

  1. ATrue
  2. BFalse
  3. CDepends on language
  4. DNone of these

Kleene's theorem part II: every TG language has an RE.

40.
★ Midterm Fall 2010

One language can represents more than one RE.

  1. ATrue
  2. BFalse
  3. CCan't be assumed
  4. DNone of given

For example (a+b)* and (a*b*)* define the same language.

41.
★ Midterm Fall 2010

The closure FA* (star on an FA) always accept ______string

  1. ANull
  2. Baa
  3. Cbb
  4. DNone of given

The closure of any language contains Λ, so FA* accepts the null string.

42.
★ Midterm Fall 2010

In FA one enter in specific stat but there is no way to leave it then state is called

  1. ADead States
  2. BWaste Baskets
  3. CDavey John Lockers
  4. DAll of above

A state with no exit is called a dead state, waste basket or Davey John locker.

43.
★ Midterm Fall 2010

Using tree structure final state represent by

  1. A*
  2. B-
  3. Cdouble circle
  4. DNone of given

Besides +, a final state may be drawn as a double circle.

44.
★ Midterm Fall 2010

"Every Infinite language is regular" this statement is

  1. ATrue
  2. BFalse

Infinite languages such as PALINDROME are not regular.

45.
★ Midterm Spring 2009

In drawing FA3 (which is equal to FA1 + FA2), a state will be declared final if

  1. AStates of both FA's are final
  2. BAt least one state is final
  3. CDepends on language
  4. DNone of the given

A word is in L1 + L2 if either FA accepts, so a combined state is final if either part is final.

46.
★ Midterm Spring 2009

The _______ machine helps in building a machine that can perform the addition of binary numbers.

  1. AIncrementing
  2. BComplementing
  3. CDecrementing
  4. DNone of the given

The incrementing (Mealy) machine is the basis for a binary adder.

47.
★ Midterm Spring 2009

"One language can be represented by more than one RE" this statement is____

  1. AFalse
  2. BTrue
  3. CCan't be assumed
  4. DNone of these

For example (a+b)* and (a*b*)* define the same language.

48.
★ Midterm Spring 2009

If FA1 accepts no string and FA2 accepts many strings, then FA1 + FA2 will be equal to

  1. AFA1
  2. BFA2
  3. CMay be both
  4. DNone of the given

The union of the empty language with L2 is L2.

49.
★ Midterm Spring 2009

"Every Infinite language is regular" this statement is

  1. ATrue
  2. BFalse
  3. CCan't be supposed
  4. DNone of these

Infinite languages such as PALINDROME are not regular.

50.
★ Midterm Spring 2009

PALINDROME can be defined by more than one regular language

  1. ATrue
  2. BFalse
  3. CBy only one RE
  4. DSome times By only one RE and Some times False

PALINDROME is nonregular, so no RE or regular language defines it.

51.
★ Midterm Spring 2009

If a language has RE, then that language can be expressed through TG.

  1. ATrue
  2. BFalse
  3. CDepends on language
  4. DNone of these

By Kleene's theorem every RE language has an FA, which is also a TG.

52.
★ Midterm Spring 2009

FA1 corresponds to r*, then FA1 must accept _______________ string.

  1. AEvery
  2. BNull
  3. COdd length
  4. DEven length

r* always contains Λ, so the FA for r* must accept the null string.

53.
★ Midterm Spring 2009

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

  1. AAccepted by FA1 AND FA2
  2. BAccepted by FA1 OR FA2
  3. CAccepted by FA1 AND/OR FA2
  4. DNone of the given options

FA1 + FA2 accepts the union: strings accepted by either machine or both.

54.
★ Midterm Spring 2009

FA3 expresses r1r2. Then initial state of FA3 will consist of

  1. AInitial state of FA2
  2. BInitial state of FA1
  3. CInitial states of both FA1 & FA2
  4. DDepends on FA's

Words of r1r2 begin with a word of r1, so FA3 starts at the initial state of FA1.

55.
★ Midterm Spring 2009

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.

  1. ATrue
  2. BFalse
  3. CDepends on language
  4. DNone of these

Final states of FA3 are those containing a final state of FA2, not the FA1-final/FA2-initial combination.