Paper Tayyari

Final Term PreparationFinal term ki tayyari

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

285 MCQs · 208 short · 21 long questions · 285 MCQs from past papers285 MCQs · 208 short · 21 long sawal · 285 MCQs past papers se

Start mock testMock test shuru karein
DoneHal kiye 0/285
– correctsahi
1.
★ Final term past paperLecture 3

Does the empty string match the regular expression |y+a|?

  1. AYes
  2. BNo

y+a matches only the one-letter strings y and a.

2.
★ Final term past paperLecture 16

Which of the following statement is true about NFA with Null String?

  1. AInfinite states
  2. BInfinite set of letters
  3. CInfinite set of transitions
  4. DTransition of null string is allowed at any stage

An NFA-Λ may move along Λ-edges without reading input.

3.
★ Final term past paperLecture 24

The strings or words which do not belong to a language is called ________ of that language

  1. AIntersection
  2. BUnion
  3. CComplement
  4. DQuotient

Strings not in L form the complement of L.

4.
★ Final term Fall 2012Lecture 25

Even-palindrome is a ________ language.

  1. ANon-regular
  2. BRegular
  3. CRegular but infinite
  4. DRegular but finite

Even-length palindromes need unbounded memory to match the two halves, so no FA accepts them.

5.
★ Final term Spring 2010Lecture 25

Which of the following is NOT a regular language?

  1. AString of 0's whose length is a perfect square
  2. BSet of all palindromes made up of 0's and 1's
  3. CString of 0's whose length is a prime number
  4. DAll of the given options

All three languages fail the pumping lemma, so none is regular.

6.
★ Final term past paperLecture 25

Set of all palindromes over {a,b} is regular

  1. ATrue
  2. BFalse

PALINDROME fails the pumping lemma, so it is nonregular.

7.
★ Final term past paperLecture 25

a^n b^n generates the ________ language

  1. Aregular
  2. Bnon regular
  3. CEQUAL and non regular
  4. DEQUAL and regular

a^n b^n is nonregular; it is only a subset of EQUAL, not EQUAL itself.

8.
★ Final term past paperLecture 25

For a non regular language there exist ________ FA

  1. AOne
  2. BAt least one
  3. CAt most one
  4. DNo

A language accepted by an FA is regular, so a nonregular language has no FA.

9.
★ Final term past paperLecture 25

A non regular language can be represented by

  1. ARE
  2. BFA
  3. CTG
  4. DNone of the given options

RE, FA and TG all describe only regular languages.

10.
★ Final term past paperLecture 25

Any language that can not be expressed by a RE is said to be regular language.

  1. ATrue
  2. BFalse

A language with no RE is nonregular.

11.
★ Final term past paperLecture 25

The language that can be expressed by any regular expression is called a Non regular language.

  1. ATrue
  2. BFalse

A language with an RE is regular.

12.
★ Final term 2013Lecture 25

Set of all palindromes over {a,b} is:

  1. ARegular
  2. BRegular and finite
  3. CRegular and infinite
  4. DNon-regular

PALINDROME fails the pumping lemma, so it is nonregular.

13.
★ Final term past paperLecture 25

For a non regular language there exist …… FA:

  1. ANO
  2. BYes

No FA accepts a nonregular language.

14.
★ Final term past paperLecture 25

A language of strings of prime length is considered to be:

  1. Aregular but infinite
  2. Bregular
  3. Cirregular
  4. Dregular but finite

PRIME is shown nonregular with the pumping lemma: pumping changes the length to a non-prime.

15.
★ Final term past paperLecture 27

Let L be an infinite language accepted by a finite automaton with N states, then for all words W in L that have length more than N there are strings x,y and Z (y being non null string) and length(x)+length(y)≤N s.t. W=xyz and all strings of the form xy^n z are in L for n=1,2,3………..

  1. ATrue
  2. BFalse

This is pumping lemma version II.

16.
★ Final term past paperLecture 30

For FA corresponding to (L1∩L2c)U(L1c∩L2) the regular expression can be determined that defines the language accepted by this :

  1. ATG
  2. BGFC
  3. CFA
  4. DGTG

The RE is found for the language accepted by that FA.

17.
★ Final term Fall 2012Lecture 31

In CFG, the symbols that can't be replaced by anything are called ________.

  1. ATerminal
  2. BNon-Terminal
  3. CProduction
  4. DAll of given

Terminals are the final letters of words and are never rewritten.

18.
★ Final term Spring 2010Lecture 31

Left hand side of a production in CFG consists of:

  1. AOne terminal
  2. BMore than one terminal
  3. COne non-terminal
  4. DTerminals and non-terminals

Every CFG production rewrites exactly one nonterminal.

19.
★ Final term Spring 2007Lecture 31

The symbols that cannot be replaced by anything are called terminals

  1. ATrue
  2. BFalse

Terminals are never rewritten.

20.
★ Final term Spring 2005Lecture 31

CFG given S → bS | Sb | aa represents language

  1. Ab*aa
  2. Baab*
  3. Cb*aab*
  4. Db*(aa)*b*

b's can be added on either side of the single aa, giving b*aab*.

21.
★ Final term past paperLecture 31

In CFG, the symbols that cannot be replaced by anything are called

  1. ATerminals
  2. BNon terminals
  3. CProductions
  4. DNone of the given options

Terminals are never rewritten.

22.
★ Final term past paperLecture 31

The grammatical rules which involves meaning of words are called:

  1. ASemantic
  2. BSytactics
  3. CAlphabets
  4. DNone of the given options

Rules about meaning are semantics; rules about form are syntax.

23.
★ Final term past paperLecture 31

The CFG S --> aSa | bSb | a | b | Λ represents the language

  1. AEVEN-EVEN
  2. BPALINDROME
  3. CEQUAL
  4. DODD-ODD

Adding the same letter on both sides around a, b or Λ builds every palindrome.

24.
★ Final term past paperLecture 31

The major problem in the earliest computers was

  1. ATo store the contents in the registers
  2. BTo display mathematical formulae
  3. CTo load the contents from the registers
  4. DTo calculate the mathematical formula

The handout says early computers had trouble handling mathematical formulae, which led to grammars and parsing.

25.
★ Final term past paperLecture 31

The production S --> SS | a | b | Λ can be expressed by RE

  1. A(a+b)+
  2. B(a+b)
  3. C(a+b)*
  4. D(ab)*

S can produce any sequence of a's and b's, including Λ.

26.
★ Final term past paperLecture 31

"CFG" stands for ________

  1. AContext Free Graph
  2. BContext Free Grammar
  3. CContext Finite Graph
  4. DContext Finite Grammar

CFG means Context Free Grammar.

27.
★ Final term past paperLecture 31

The high level language is converted into assembly language codes by a program called compiler.

  1. ATRUE
  2. BFALSE

A compiler translates high-level code into lower-level code.

28.
★ Final term past paperLecture 31

Grammatical rules which involve the meaning of words are called ________

  1. ASemantics
  2. BSyntactic
  3. CBoth a and b
  4. DNone of given

Rules about meaning are semantics.

29.
★ Final term past paperLecture 31

Grammatical rules which do not involve the meaning of words are called ________

  1. ASemantics
  2. BSyntactic
  3. CBoth a and b
  4. DNone of given

Rules about form only are syntactic rules.

30.
★ Final term past paperLecture 31

The symbols that must be replaced by other things are called ________

  1. AProductions
  2. BTerminals
  3. CNon-terminals
  4. DNone of given

Nonterminals must be rewritten before a word is reached.

31.
★ Final term past paperLecture 31

The grammatical rules are often called ________

  1. AProductions
  2. BTerminals
  3. CNon-terminals
  4. DNone of given

Grammar rules are called productions.

32.
★ Final term past paperLecture 31

The terminals are designated by ________ letters, while the non-terminals are designated by ________ letters.

  1. ACapital, bold
  2. BSmall, capital
  3. CCapital, small
  4. DSmall, bold

By convention terminals are lowercase and nonterminals uppercase.

33.
★ Final term past paperLecture 31

The language generated by ________ is called Context Free Language (CFL).

  1. AFA
  2. BTG
  3. CCFG
  4. DTGT

A CFL is the language generated by a CFG.

34.
★ Final term past paperLecture 31

Σ = {a,b} Productions S → XaaX, X → aX, X → bX, X → Λ. This grammar defines the language expressed by ________

  1. A(a+b)*aa(a+b)*
  2. B(a+b)*a(a+b)*a
  3. C(a+b)*aa(a+b)*aa
  4. D(a+b)*ab(a+b)*

X generates (a+b)*, so XaaX gives (a+b)*aa(a+b)*.

35.
★ Final term past paperLecture 31

Consider the Following CFG: (NOTE: Λ means NULL) S->Xa X->aX|bX|Λ above given CFG can be represented by RE

  1. Aa*b*
  2. Ba*b*a
  3. C(a+b)*a
  4. Da(a+b)*a

X gives (a+b)*, followed by a final a.

36.
★ Final term past paperLecture 31

The langue generated by CFG is called Context free language (CFL)

  1. AFalse
  2. BTrue

A CFG generates a context free language.

37.
★ Final term past paperLecture 31

The symbols that can't be replaced by anything are called -----------------

  1. AProductions
  2. BTerminals
  3. CNon-terminals
  4. DAll of above

Terminals cannot be replaced.

38.
★ Final term past paperLecture 31

S → aXb|bXa X → aX|bX|Λ The given CFG generates the language of strings in English

  1. ABeginning and ending in different letters
  2. BBeginning and ending in same letter
  3. CHaving even-even language
  4. DNone of given

Words are a…b or b…a.

39.
★ Final term past paperLecture 31

One language can have ……… CFG(s)

  1. AAt least one
  2. BAt least two
  3. CAt least three
  4. DNone of them

A CFL has at least one (in fact many) CFGs.

40.
★ Final term past paperLecture 31

The language generated by the CFG is called the language ……by the CFG

  1. AProduced
  2. BNull string
  3. CPumping lemma
  4. DNon of then

It is the language produced (generated) by the CFG.

41.
★ Final term past paperLecture 31

In CFG, the symbols that cannot be replaced by anything are called:

  1. ANone terminals
  2. BInfinite
  3. CFinite
  4. DTerminals

Terminals cannot be replaced.

42.
★ Final term past paperLecture 31

The production S --> SS | a | b | Λ can be expressed by RE:

  1. A(a+b)+
  2. Ba-b
  3. C(a-b)+
  4. DNone of them

It generates (a+b)* (including Λ), which is not listed.

43.
★ Final term past paperLecture 31

The same non terminals can be written in single line if they have more than one..........

  1. AProductions
  2. BRegular production
  3. CNone regular production

Productions with the same left side can be combined with |.

44.
★ Final term past paperLecture 31

There is at least one production that has one........on its left side:

  1. ATerminal
  2. BInfinite
  3. CNone Terminal
  4. DAll of above

A CFG has at least one production with the start non-terminal S on its left.

45.
★ Final term past paperLecture 31

Left hand side of CFG may consist of:

  1. AOne terminal
  2. BMore than one terminal
  3. COne non-terminal
  4. DTerminals and non-terminals

One non-terminal on the left side.

46.
★ Final term past paperLecture 31

The language generated by CFG is called ________.

  1. AInfinite
  2. BContext Free Language (CFL)
  3. CRegular
  4. DFinite

By definition the language generated by a context free grammar is a context free language.

47.
★ Final term past paperLecture 31

Left hand side of a production in Context free grammar (CFG) consists of ________.

  1. AOne terminal
  2. BMore than one terminal
  3. COne non-terminal
  4. DTerminals and non-terminals

In a CFG every production has exactly one nonterminal on its left side.

48.
★ Final term Spring 2007Lecture 32

Syntax tree or Generation tree or Derivation tree are same tree

  1. ATrue
  2. BFalse

These are three names for the same tree that shows a derivation.

49.
★ Final term Spring 2005Lecture 32

A Total Language Tree has

  1. AAll languages over Σ
  2. BAll strings over Σ
  3. CAll words of all languages over Σ
  4. DAll words of one language over Σ

The total language tree of a CFG shows every derivation, so its leaves are all words of that one language.

50.
★ Final term past paperLecture 32

The …………. is said to be ambiguous if there exist at least one word of its language that can be generated by the different production tree .

  1. ACFL
  2. BCFG
  3. CGTG
  4. DNone of the given

Ambiguity is a property of a CFG.

51.
★ Final term past paperLecture 32

The CFG is said to be ambiguous if there exists atleast one word of its language that can be generated by the different production trees,

  1. ATRUE
  2. BFALSE

That is the definition of ambiguity.

52.
★ Final term past paperLecture 32

Consider the following CFG S→aS|bS|aaS|Λ it can be observed that the word aaa can be derived from more than:

  1. Aone production tree
  2. Btwo producton tree
  3. CTotal language tree
  4. DAll of above

aaa has several trees (a·a·a, aa·a, a·aa), so it has more than one production tree.

53.
★ Final term past paperLecture 32

Any word generated by given CFG cannot also be expressed by Syntax tree or Generation tree or Derivation tree as well

  1. Atrue
  2. Bfalse

Every derivation can be drawn as a tree.

54.
★ Final term past paperLecture 33

In polish notation, (o-o-o) is the abbreviation of ________?

  1. AOperand - Operator - Operand
  2. BOperand - Operand- Operator
  3. COperator -Operand - Operand
  4. DOperand -Operand - Operand

Polish (prefix) notation writes the operator before its two operands.

55.
★ Final term Fall 2012Lecture 34

Which of the following is a regular Context Free Grammar:

  1. AS → abS | baS | Λ
  2. BS → aSb | baS | Λ
  3. CS → abS | bSa | Λ
  4. DS → aSb | Sa | Λ

In S → abS | baS | Λ each production is terminals followed by at most one nonterminal at the right end.

56.
★ Final term Spring 2006Lecture 34

Semi-word is a string having some terminals and one non-terminal at the right of string.

  1. ATrue
  2. BFalse

A semiword is terminals followed by exactly one nonterminal at the end.

57.
★ Final term Spring 2006Lecture 34

CFG may also represent a regular language.

  1. ATrue
  2. BFalse

Every regular language has a CFG (a regular grammar).

58.
★ Final term past paperLecture 34

The language generated by that CFG is regular if ________

  1. ANonterminal → semi word
  2. BNonterminal → word
  3. CBoth a and b
  4. DNone of given

A CFG whose productions are all nonterminal → semiword or word is a regular grammar.

59.
★ Final term past paperLecture 34

The CFG which generates the regular language is called

  1. ARegular expression
  2. BFinite Automata
  3. CRegular grammar
  4. DNone of the given options

A CFG for a regular language in semiword form is a regular grammar.

60.
★ Final term past paperLecture 34

The language generated by that CFG is regular if _________

  1. ANo terminal → semi word
  2. BNo terminal → word
  3. CBoth a and b
  4. DNone of given

If every production is non-terminal → semiword or non-terminal → word, the language is regular.

61.
★ Final term past paperLecture 34

If every production in CFG is one of the following forms Nonterminal → semi word, Nonterminal → word. Then the language generated by that CFG is :

  1. ARegular
  2. BNonregular
  3. CFinite
  4. DInfinite

Such a grammar is a regular grammar, so the language is regular.

62.
★ Final term past paperLecture 34

CFG is said to be a regular grammar if it generates the regular language i.e.a CFG is said to be a regular grammar in which each production is one of the:

  1. AThree forms
  2. BOne form
  3. CFour forms
  4. DTwo forms

Non-terminal → semiword or non-terminal → word.

63.
★ Final term past paperLecture 35

In the null production N --> Λ, N is a

  1. ATerminal
  2. BNon terminal
  3. CWord
  4. DNone of the given options

The left side of any CFG production is a nonterminal.

64.
★ Final term past paperLecture 35

The production of the form: Nonterminal-> Λ is said to be ________ production

  1. ANULL
  2. BUNIT
  3. CChomsky form production
  4. DNone of the given options

A production with Λ on the right is a null production.

65.
★ Final term past paperLecture 35

If a CFG has a null production, then it is ________

  1. APossible to construct another CFG without null production accepting the same language with the exception of the word Λ
  2. BNot possible to construct another CFG without null production accepting the same language with the exception of the word Λ
  3. CCalled NULL CFG
  4. DCalled Chomsky Normal Form (CNF)

Null productions can be removed, losing at most the word Λ.

66.
★ Final term past paperLecture 35

The production of the form nonterminal → Λ is said to be null production.

  1. ATRUE
  2. BFALSE

This is the definition of a null production.

67.
★ Final term past paperLecture 35

If a CFG has a null production, then it is possible to construct another CFG accepting the same language without null production

  1. ATRUE
  2. BFALSE

Null productions can be removed, except that the word Λ may be lost.

68.
★ Final term past paperLecture 35

The production of the form no terminal → Λ is said to be null production.

  1. ATRUE
  2. BFALSE

Non-terminal → Λ is a null production.

69.
★ Final term past paperLecture 35

A production is called null able production if it is of the form N → Λ

  1. ATRUE
  2. BFALSE

The handout counts N → Λ (or any derivation of Λ from N) as nullable.

70.
★ Final term Fall 2012Lecture 36

If a CFG has only productions of the form nonterminal → string of two nonterminals or nonterminal → one terminal then the CFG is said to be in ________

  1. AChomsky Normal Form
  2. BAmbiguous Form
  3. CLeft Aligned Form
  4. DRight Aligned Form

These two production forms are exactly the definition of Chomsky Normal Form.

71.
★ Final term Fall 2012Lecture 36

________ and ________ are removed in order to make a CFG in Chomsky Normal Form(CNF).

  1. ANull, nullable productions
  2. BNullable , unit productions
  3. CNull, unit productions
  4. DString of length 0, null

Converting to CNF first removes null productions and unit productions.

72.
★ Final term past paperLecture 36

Identify the TRUE statement about following CFG: S -> SB|AB A -> CC B -> b C -> a

  1. AThe given CFG has 8 Nonterminals
  2. BThe given CFG has 8 Terminals
  3. CThe given CFG is in CNF
  4. DThe given CFG is not in CNF

Every production is either two nonterminals or one terminal, so it is in CNF.

73.
★ Final term past paperLecture 36

CNF is stands for

  1. AContext Normal Form
  2. BComplete Normal Form
  3. CChomsky Normal Form
  4. DCompared Null Form

CNF means Chomsky Normal Form.

74.
★ Final term past paperLecture 36

All NonNull words of the CFL can be generated by the corresponding CFG which is in CNF i.e the grammar in CNF will generate the same language except the :

  1. Astring
  2. Bregular language
  3. Cnull string
  4. Dnon of above

A CNF grammar has no null productions, so only Λ is lost.

75.
★ Final term Fall 2012Lecture 37

We can also represent an FA using different states e.g Accept state; Reject state, Read state etc. The ________ state behaves as final state of an FA

  1. AAccept
  2. BPop
  3. CPush
  4. DReject

In the new format of an FA, reaching ACCEPT means the input is accepted, like a final state.

76.
★ Final term Fall 2012Lecture 37

________ where the input string is placed before it is run, is called ________

  1. AData tape
  2. BInput Tape
  3. COutput Tape
  4. DMagnetic tape

The input string is written on the INPUT TAPE before the machine runs.

77.
★ Final term Fall 2012Lecture 37

A read state can have ________ outgoing edge/ edges.

  1. A1
  2. B2
  3. C3
  4. DAny number of

A READ state may branch on any number of letters, including blank.

78.
★ Final term past paperLecture 37

Halt states are

  1. AStart and Accept
  2. BAccept and Reject
  3. CStart and Reject
  4. DRead and Reject

The machine stops at ACCEPT or REJECT, so these are the halt states.

79.
★ Final term past paperLecture 37

The input string is placed, before it runs, in

  1. AStack
  2. BMemory
  3. CTape
  4. DRam

The input string is written on the input tape.

80.
★ Final term past paperLecture 37

The locations into which we put the input letters on "Input Tape" are called ________

  1. Awords
  2. Balphabets
  3. Ccells
  4. Delements

The input tape is divided into cells, one letter per cell.

81.
★ Final term past paperLecture 37

________ states are called the halt states.

  1. AACCEPT and REJECT
  2. BACCEPT and READ
  3. CACCEPT AND START
  4. DACCEPT AND WRITE

The machine stops at ACCEPT or REJECT.

82.
★ Final term past paperLecture 37

The part of an FA, where the input string is placed before it is run, is called ________

  1. AState
  2. BTransition
  3. CInput Tape
  4. DOutput Tape

The input string is written on the input tape.

83.
★ Final term past paperLecture 37

In new format of an FA (discussed in lecture 37), This state is like dead-end non final state

  1. AACCEPT
  2. BREJECT
  3. CSTART
  4. DREAD

REJECT halts without accepting, like a dead non-final state.

84.
★ Final term past paperLecture 37

In new format of an FA This state is like dead-end non final state:

  1. AACCEPT
  2. BREJECT
  3. CSTART
  4. DREAD

REJECT works like a dead-end non-final state.

85.
★ Final term Spring 2010Lecture 38

Like TG, a PDA can also be non-deterministic

  1. ATrue
  2. BFalse

A PDA may have several edges with the same label from a READ or POP state.

86.
★ Final term past paperLecture 38

A PDA is called nondeterministic PDA if ________

  1. AThere are more than one outgoing edges at READ or POP states with one label
  2. BThere are more than one PUSH states
  3. CThere are more than one POP states
  4. DAll of the given options

Nondeterminism means a choice of edges with the same label at a READ or POP state.

87.
★ Final term past paperLecture 38

The PDA is called non-deterministic PDA when there are more than one out going edges from ________ state

  1. ASTART or READ
  2. BPOP or REJECT
  3. CREAD or POP
  4. DPUSH or POP

Branching on the same label happens only at READ or POP states.

88.
★ Final term past paperLecture 38

Identify the TRUE statement:

  1. AA PDA is non-deterministic, if there are more than one READ states in PDA
  2. BA PDA is never non-deterministic
  3. CLike TG, A PDA can also be non-deterministic
  4. DA PDA is non-deterministic, if there are more than one REJECT states in PDA

A PDA may be nondeterministic, just like a TG.

89.
★ Final term past paperLecture 38

In nondeterministic PDA a string is supposed to be accepted, if there exists at least one path traced by the string, leading to ________ state.

  1. AACCEPT
  2. BREJECT
  3. CSTART
  4. DREAD

A nondeterministic PDA accepts if some path reaches ACCEPT.

90.
★ Final term Fall 2012Lecture 39

For every Context Free Grammar (CFG), we can make the corresponding ________ .

  1. AFA
  2. BTG
  3. CPDA
  4. DRegular Grammar

Every CFG can be converted into a PDA that accepts the same language.

91.
★ Final term past paperLecture 39

Choice of path can be determined by left most derivation of the string belonging to CFL at ________ state

  1. AAccept
  2. BReject
  3. CPush
  4. DPOP

In the PDA built from a CFG the branching happens at the POP state, and the leftmost derivation picks the branch.

92.
★ Final term past paperLecture 43

Language which are context –free are called Non –CFL:

  1. ATrue
  2. BFalse

Non-CFLs are languages that are not context free.

93.
★ Final term past paperLecture 43

A nonterminal is said to be self-embedded, if in a given derivation of a word, it ever occurs as a tree ________ of itself.

  1. Aascendant
  2. Bdescendant
  3. Ctop
  4. Dbottom

A self-embedded nonterminal appears again below itself in the derivation tree, i.e. as its own descendant.

94.
★ Final term Fall 2012Lecture 44

The process of finding the derivation of the word generated by particular grammar is called

  1. AProcessing
  2. BParsing
  3. CProgramming
  4. DPlanning

Finding a derivation (parse tree) of a word in a grammar is called parsing.

95.
★ Final term Fall 2012Lecture 44

Chomsky normal form (CYK) algorithm was proposed by ________ .

  1. AJohn Cocke
  2. BJames Cock
  3. CDaniel I.A.
  4. DJohn Weiss

The CYK algorithm is named after Cocke, Younger and Kasami; John Cocke is the C.

96.
★ Final term past paperLecture 44

The process of finding the derivation of word generated by particular grammar is called :

  1. APLUS TIMING
  2. BParsing
  3. CHALT
  4. DAll of above

Finding a derivation is parsing.

97.
★ Final term past paperLecture 44

CYK algorithm was invented by John Cocke and later was published by ____

  1. ATalik Khon and Daniel H
  2. BTandao Kasami and Daniel H
  3. CTandao Dagger and Daniel H
  4. DTalik Khon

The CYK algorithm is named after Cocke, Younger and Kasami; Tadao Kasami and Daniel H. Younger published it.

98.
★ Final term past paperLecture 44

There are different parsing techniques, including ________

  1. ATop down parsing
  2. BBottom up parsing
  3. CParsing technique for particular grammar of arithmetic expression
  4. DAll of these

Top-down, bottom-up and the technique for arithmetic expression grammars are all parsing techniques.

99.
★ Final term past paperLecture 44

CYK algorithm was invented by John Cocke and later was published by ____

  1. ATalik Khon and Daniel H
  2. BTadao Kasami and Daniel H
  3. CTandao Dagger and Daniel H
  4. DTalik Khon

The CYK algorithm is named after Cocke, Younger and Kasami; it was later published by Tadao Kasami and Daniel H. Younger.

100.
★ Final term Fall 2012Lecture 45

An FSM can be considered as TM

  1. AOf finite tape length, rewinding capability and unidirectional tape movement
  2. BOf finite tape length, without rewinding capability and bidirectional tape movement
  3. COf finite tape length, rewinding capability and bidirectional tape movement
  4. DOf finite tape length, without rewinding capability and unidirectional tape movement

An FSM reads its finite input once, left to right, without going back.

101.
★ Final term Fall 2012Lecture 45

The above machine (edges labelled (a,a,R), (b,b,R)) is a/an ________

  1. AFinite Automata
  2. BTuring machine
  3. CFA
  4. DTG

Edge labels of the form (read, write, move) belong to a Turing machine.

102.
★ Final term Spring 2010Lecture 45

Who did not invent the Turing machine?

  1. AAlan Turing
  2. BA. M. Turing
  3. CTuring
  4. DNone of these

Alan Turing, A. M. Turing and Turing are the same person, who invented it.

103.
★ Final term Spring 2010Lecture 45

Which statement is true?

  1. AThe tape of turing machine is infinite.
  2. BThe tape of turing machine is finite.
  3. CThe tape of turing machine is infinite when the language is regular
  4. DThe tape of turing machine is finite when the language is nonregular.

A Turing machine has a tape that is infinite in one direction.

104.
★ Final term Spring 2010Lecture 45

TM is more powerful than FSM because

  1. AThe tape movement is confined to one direction
  2. BIt has no finite state control
  3. CIt has the capability to remember arbitrary long sequences of input symbols
  4. DNone of these

The read-write tape gives a TM unlimited memory, which an FSM lacks.

105.
★ Final term Spring 2005Lecture 45

What Turing Machine does not have?

  1. AStack
  2. BTape
  3. CHead
  4. DWord

A Turing machine has a tape and a read-write head but no stack.

106.
★ Final term past paperLecture 45

A program which is the set of rules which show that which state is to be entered when a letter is read form the :

  1. ATAPE
  2. BHALT
  3. CTM
  4. DNone of above

A TM program says which state to enter on reading a letter from the TAPE.

107.
★ Final term past paperLecture 45

Can a turing machine's head ever be in the same location in two successive steps?

  1. AYes
  2. BYes but only in finite languages
  3. CNo
  4. DYes but only in infinite langauges

In this model the head moves one cell left or right on every step.

108.
★ Final term past paperLecture 45

In ________ there are Finite set of states containing exactly one START state and some (may be none) HALT states that cause execution to terminate, when the HALT states are entered.

  1. ATG
  2. BTuring Machine
  3. CGTG
  4. DFinite Automata

START and HALT states are part of the definition of a Turing machine.

109.
★ Final term Fall 2012

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

  1. Aaaabbb
  2. Baabbbb
  3. Caabbaa
  4. Dbbaabbbb

Every word of Σ* is built from blocks aa and bb, so it cannot contain an odd run like aaa followed by bbb.

110.
★ Final term Fall 2012

"One language can have ________ TG's".

  1. AOnly one
  2. BOnly two
  3. CMore than one
  4. DOnly three

Many different TGs can accept the same language.

111.
★ Final term Fall 2012

According to 1st part of the Kleene's theorem, If a language can be accepted by an FA then it can be accepted by a ________ as well.

  1. AFA
  2. BCFG
  3. CGTG
  4. DTG

Part I of Kleene's theorem states that every language accepted by an FA is accepted by a TG.

112.
★ Final term Fall 2012

If L is a regular language then, Lc is also a ________ language.

  1. ARegular
  2. BNon-regular
  3. CRegular but finite
  4. DNone of the given

Swapping final and non-final states of an FA for L gives an FA for its complement.

113.
★ Final term Fall 2012

Pumping lemma is generally used to prove that:

  1. AA given language is infinite
  2. BA given language is not regular
  3. CWhether two given regular expressions of a regular language are equivalent or not
  4. DNone of these

Showing that some long word cannot be pumped proves that a language is not regular.

114.
★ Final term Fall 2012

If the FA has N states, then test the words of length less than N. If no word is accepted by this FA, then it will ________ word/words.

  1. Aaccept all
  2. Baccept no
  3. Caccept some
  4. Dreject no

If an FA with N states accepts any word, it accepts one shorter than N, so none accepted means the language is empty.

115.
★ Final term Fall 2012

Which of the following is a regular language?

  1. AString of odd number of zeroes
  2. BSet of all palindromes made up of 0's and 1's
  3. CString of 0's whose length is a prime number
  4. DAll of these

Odd number of zeroes is accepted by a two-state FA, while the other two languages are nonregular.

116.
★ Final term Fall 2012

Which of the following pairs of regular expressions are equivalent?

  1. A1(001)* and (10)*10
  2. Bx(xx)* and (x)*x
  3. CX+ and X*
  4. DX+ and X*X+

X*X+ needs at least one X and allows any number more, which is exactly X+.

117.
★ Final term Fall 2012

An alphabet Σ is valid if

  1. ANo letter of Σ appears in middle of any other letter
  2. BNo letter of Σ appears at end of any other letter
  3. CNo letter of Σ appears at start of any other letter
  4. DNo letter of Σ appears at end or middle of any other letter

If no letter is the start of another letter, every string can be tokenized without ambiguity.

118.
★ Final term Fall 2012

Which of the following statement is true

  1. AThe length of the output string is greater than length of input string in moore machine.
  2. BThe length of the output string is greater than length of input string in mealy machine.
  3. CThe length of the output string is equal to length of input string in moore machine.
  4. DThe length of the output string is less than length of input string in mealy machine.

A Moore machine prints a character in the start state before reading input, so its output is one longer than the input.

119.
★ Final term Fall 2012

Alphabet Σ = {a, bc, cc} has number of letters

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

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

120.
★ Final term Fall 2012

If r1 is a regular expression then r1* is a ________

  1. AGTG
  2. BNFA
  3. CFA
  4. DRE

The Kleene star of a regular expression is again a regular expression by definition.

121.
★ Final term Fall 2012

We cannot write regular expressions for all ________ .

  1. AFA's
  2. BTG's
  3. CNFA's
  4. DCFG's

Every FA, TG and NFA has an RE by Kleene's theorem, but some CFGs generate nonregular languages.

122.
★ Final term Fall 2012

The language of Palindromes defined over an alphabet set {a, b} can be recognized by ________.

  1. AFA
  2. BNFA
  3. CTG
  4. DPDA

PALINDROME is nonregular but context free, so a PDA is needed.

123.
★ Final term Fall 2012

(Σ* - L) represent the ________ of a language L.

  1. AComplement
  2. BKleene's closure
  3. CUnion
  4. Dintersection

All strings over Σ that are not in L form the complement of L.

124.
★ Final term Fall 2012

If we have two transition graphs then their union will be expressed by

  1. Ataking a common start state and joining them by two null transitions
  2. Bjust connecting both start states by null transitions
  3. Cconnecting final state of first TG to the initial state of second TG
  4. Dconnecting the final state of first TG to the final state of second TG

A new start state with Λ-edges to both old start states lets a word follow either TG.

125.
★ Final term Fall 2012

If L1 and L2 are expressed by regular languages then L1 + L2 is also a ________ Language.

  1. ARegular
  2. BIr-regular
  3. CPDA
  4. DHybrid

Regular languages are closed under union.

126.
★ Final term Fall 2012

Finite Automation (FA) and Nondeterministic Finite Automation (NFA) are equivalent if

  1. AFA and NFA accept the same language
  2. BFA shape is same like an NFA
  3. CFA accept the null string also
  4. DNFA accept the null string also

Two machines are equivalent when they accept the same language.

127.
★ Final term Fall 2012

________ is always Deterministic.

  1. AFinite Automation
  2. BTransition Graph
  3. CGeneralize Transition Graph
  4. DNon-deterministic finite automation

An FA has exactly one transition for each letter from each state, so it is deterministic.

128.
★ Final term Spring 2010

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

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

The expression is r1 followed by r2, i.e. their concatenation.

129.
★ Final term Spring 2010

"One language can be expressed by more than one FA". This statement is ________

  1. ATrue
  2. BFalse
  3. CSome times true & sometimes false
  4. DNone of these

Different FAs, e.g. with extra states, can accept the same language.

130.
★ Final term Spring 2010

A regular language:

  1. AMust be finite
  2. BMust be infinite
  3. CCan be finite or infinite
  4. DMust be finite and cannot be infinite

Every finite language is regular and infinite ones like a* are regular too.

131.
★ Final term Spring 2010

Every regular expression can be expressed as CFG but every CFG cannot be expressed as a regular expression. This statement is:

  1. ADepends on the language
  2. BNone of the given options
  3. CTrue
  4. DFalse

Regular languages are a proper subset of context-free languages.

132.
★ Final term Spring 2010

Consider the language L of strings, defined over Σ = {a,b}, ending in a

  1. AThere are finite many classes generated by L, so L is regular
  2. BThere are infinite many classes generated by L, so L is regular
  3. CThere are finite many classes generated by L, so L is non-regular
  4. DThere are infinite many classes generated by L, so L is non-regular

Strings ending in a split Σ* into two classes, and by Myhill-Nerode finitely many classes means regular.

133.
★ Final term Spring 2010

The word 'formal' in formal languages means

  1. AThe symbols used have well defined meaning
  2. BThey are unnecessary, in reality
  3. COnly the form of the string of symbols is significant
  4. DNone of these

Formal languages deal with the form (syntax) of strings, not their meaning.

134.
★ Final term Spring 2010

Choose the correct statement.

  1. AA Mealy machine generates no language as such
  2. BA Moore machine generates no language as such
  3. CA Mealy machine has no terminal state
  4. DAll of these

Moore and Mealy machines only translate input to output; they have no final states and define no language.

135.
★ Final term Spring 2010

If L1 and L2 are expressed by regular expressions r1 and r2, respectively then the language expressed by r1 + r2 will be ________

  1. ARegular
  2. BIr-regular
  3. CCan't be decided
  4. DAnother Language which is not listed here

r1 + r2 is a regular expression, so its language is regular.

136.
★ Final term Spring 2010

The language of all words (made up of a's and b's) with at least two a's can not be described by the regular expression.

  1. Aa(a+b)*a(a+b)*(a+b)*ab*
  2. B(a+b)*ab*a(a+b)*
  3. Cb*ab*a(a+b)*
  4. Dnone of these

Option a forces the word to start with a and have three a's, so it misses words like baa; b and c describe the language.

137.
★ Final term Spring 2010

In FA, if one enters in a specific state but there is no way to leave it, then that specific state is called

  1. ADead State
  2. BWaste Basket
  3. CDavey John Locker
  4. DAll of these

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

138.
★ Final term Spring 2010

Choose the incorrect (FALSE) statement.

  1. AA Mealy machine generates no language as such
  2. BA Mealy machine has no terminal state
  3. CFor a given input string, length of the output string generated by a Moore machine is not more than the length of the output string generated by that of a Mealy machine
  4. DAll of these

A Moore machine prints one more character than a Mealy machine for the same input, so c is false.

139.
★ Final term Spring 2010

Choose the incorrect statement:

  1. A(a+b)*aa(a+b)* generates Regular language.
  2. BA language consisting of all strings over Σ={a,b} having equal number of a's and b's is a regular language
  3. CEvery language that can be expressed by FA can also be expressed by RE
  4. DNone of these

EQUAL needs unbounded counting, so it is not regular; the other statements are true.

140.
★ Final term Spring 2007

PDA is only used to represent a regular language.

  1. ATrue
  2. BFalse

PDAs accept all context-free languages, including nonregular ones.

141.
★ Final term Spring 2007

If L is a regular language then LC is also a regular language.

  1. ATrue
  2. BFalse

Regular languages are closed under complement.

142.
★ Final term Spring 2007

A production of the form non-terminal → string of two non-terminal is called a live Production.

  1. ATrue
  2. BFalse

In the handouts a live production has the form nonterminal → two nonterminals.

143.
★ Final term Spring 2007

We can find a CFG corresponding to a DFA.

  1. ATrue
  2. BFalse

Every FA language is regular and every regular language has a (regular) CFG.

144.
★ Final term Spring 2007

A CFG is said to be ambiguous if there exists at least one word of its language that can be generated by different production trees

  1. ATrue
  2. BFalse

This is the definition of an ambiguous CFG.

145.
★ Final term Spring 2007

The production of the form non-terminal → one non-terminal is called unit production

  1. ATrue
  2. BFalse

A unit production has one nonterminal on each side.

146.
★ Final term Spring 2007

DFA and PDA are equal in power.

  1. ATrue
  2. BFalse

A PDA accepts nonregular context-free languages that no DFA accepts.

147.
★ Final term Spring 2006

A production of the form non-terminal → non-terminal non-terminal is called a dead Production.

  1. ATrue
  2. BFalse

A dead production has the form nonterminal → terminal; two nonterminals on the right make a live production.

148.
★ Final term Spring 2006

Two FAs are equivalent if they have same no. of states.

  1. ATrue
  2. BFalse

FAs are equivalent when they accept the same language, not when they have the same number of states.

149.
★ Final term Spring 2006

There exist exactly two different derivations in an ambiguous CFG for a word.

  1. ATrue
  2. BFalse

Ambiguity needs at least two different trees for some word, not exactly two.

150.
★ Final term Spring 2006

Regular languages are closed under Union, Concatenation and Kleene star.

  1. ATrue
  2. BFalse

If r1 and r2 are REs then r1 + r2, r1r2 and r1* are REs too.

151.
★ Final term Spring 2006

PDA is stronger than FA.

  1. ATrue
  2. BFalse

PDAs accept every regular language plus nonregular context-free languages.

152.
★ Final term past paper

The reverse of the string sbfsbb over { sb, f, b }

  1. Abbsfbs
  2. Bbsbfsb
  3. Csbbfsb
  4. Dbsfbsb

Tokens are sb, f, sb, b; reversed they give b sb f sb = bsbfsb.

153.
★ Final term past paper

Two languages are said to belong to same class if they end in the same state when they run over an FA, that state

  1. AMust be final state
  2. BMay be final state or not
  3. CMay be start or not
  4. DNone of the given options

Strings are in the same class if they end in the same state, whether or not it is final.

154.
★ Final term past paper

According to Myhill Nerode theorem, if L generates finite no. of classes then L is ________

  1. AFinite
  2. BInfinite
  3. CRegular
  4. DNon Regular

Myhill-Nerode: finitely many classes means L is regular.

155.
★ Final term past paper

If the intersection of two regular languages is regular then the complement of the intersection of these two languages is also regular

  1. ATrue
  2. BFalse

The complement of a regular language is regular.

156.
★ Final term past paper

In pumping lemma theorem (x y^n z) the range of n is

  1. An=1,2,3,4...
  2. Bn=0,1,2,3,4....
  3. Cn=-3,-2,-1,0,1,2,3,4
  4. Dn=-3,-2,-1,1,2,3,4

The handout version states that xy^n z is in L for n = 1, 2, 3, ...

157.
★ Final term past paper

The complement of a regular language is also a regular

  1. ATrue
  2. BFalse

Regular languages are closed under complement.

158.
★ Final term past paper

For language L defined over {a, b},then L partitions {a, b}* into ________ classes

  1. AInfinite
  2. BFinite
  3. CDistinct
  4. DNon distinct

Myhill-Nerode: L partitions Σ* into distinct classes.

159.
★ Final term past paper

If an FA accept a word then there must exist a path from

  1. AInitial to final state
  2. BInitial to each state
  3. CInitial to each state but not to final state
  4. DInitial to final state by traversing each state

Acceptance means the word traces a path from the initial state to a final state.

160.
★ Final term past paper

If an FA already accepts the language expressed by the closure of certain RE, then the given FA is the required FA.

  1. ATrue
  2. BFalse

An FA that already accepts r* needs no change to serve as the FA for r*.

161.
★ Final term past paper

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

  1. ATrue
  2. BFalse

If R = Σ*, then L ∪ R = Σ* is regular for any L, even a nonregular one.

162.
★ Final term past paper

FA corresponding to an NFA can be built by introducing an empty state for a letter having

  1. Ano transition at certain state
  2. Bone transition at certain state
  3. Ctwo transition at certain state
  4. Dmore than two transitions at certain state

A missing transition in the NFA becomes a move to an empty (dead) state in the FA.

163.
★ Final term past paper

(a* + b*)* = (a + b)* this expression is ________

  1. ATrue
  2. BFalse

a* + b* contains a and b, so its closure is all strings.

164.
★ Final term past paper

If S = { x }, then S* will be

  1. A{x,xx,xxx,xxxx,...}
  2. B{Λ,x,xx,xxx,xxxx,...}

The Kleene star always includes the null string Λ.

165.
★ Final term past paper

The states in which there is no way to leave after entry are called

  1. ADavey John Lockers
  2. BDead States
  3. CWaste Baskets
  4. DAll of the given options

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

166.
★ Final term past paper

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

  1. Aabbbab
  2. Bbbba
  3. Cababbb
  4. Dbbbbab

bbba cannot be split into ab and bb blocks; the other three can.

167.
★ Final term past paper

According to theory of automata there are ________ types of languages

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

The course divides languages into formal and informal languages.

168.
★ Final term past paper

What do automata mean?

  1. ASomething done manually
  2. BSomething done automatically

Automaton means something that works automatically.

169.
★ Final term past paper

What is false about the term alphabet?

  1. AIt is a finite set of symbols.
  2. BIt is usually denoted by Greek letter sigma
  3. CIt can be an empty set.
  4. DStrings are made up of its elements

An alphabet is a finite non-empty set of letters.

170.
★ Final term past paper

Formal is also known as ________

  1. ASyntactic language
  2. BSemantic language
  3. CInformal language
  4. DNone of these

Formal languages are also called syntactic languages.

171.
★ Final term past paper

Following are types of languages

  1. AFormal Languages (Syntactic languages)
  2. BInformal Languages (Semantic languages)
  3. CBoth
  4. DNone of above

The two types of languages are formal and informal.

172.
★ Final term past paper

Consider the following production (of a CFG): S->XYZ Here ________ is left most nonterminal in working string. Note: S, X, Y and Z are all nonterminals

  1. AS
  2. BX
  3. CY
  4. DZ

In the working string XYZ the first nonterminal from the left is X.

173.
★ Final term past paper

A PDA consists of the following:

  1. AAn alphabet (Sigma) of input letters.
  2. BAn input TAPE with infinite many locations in one direction
  3. COne START state with only one out-edge and no in-edge
  4. DAll of the given options

All three are listed parts of a PDA.

174.
★ Final term past paper

The unit and null productions can be deleted from a CFG

  1. ATrue
  2. BFalse

Both can be removed while keeping the language (except possibly Λ).

175.
★ Final term past paper

The structure given below is called ________ S -> aA|bB A -> aS|a B -> bS|b

  1. ARE
  2. BTG
  3. CCFG
  4. DPDA

A set of productions with a start symbol is a context-free grammar.

176.
★ Final term past paper

Which of the following states is not part of PDA

  1. ASTART
  2. BACCEPT
  3. CWRITE
  4. DREJECT

A PDA has START, READ, PUSH, POP, ACCEPT and REJECT states but no WRITE state.

177.
★ Final term past paper

The production of the form: nonterminal --> one nonterminal is called the ________

  1. AUnit production
  2. BNULL production
  3. CTerminal production
  4. DNon Terminal production

One nonterminal on each side is a unit production.

178.
★ Final term past paper

A ________ is the one for which every input string has a unique path through the machine.

  1. ADeterministic PDA
  2. Bnondeterministic PDA
  3. CPUSHDOWN store
  4. DInput Tape

Deterministic means each input string has exactly one path.

179.
★ Final term past paper

The CFG is said to be ambiguous if there exist at least one word of its language that can be generated by the ________ production trees

  1. AOne
  2. BTwo
  3. CMore than one
  4. DAt most one

Ambiguous means some word has more than one production tree.

180.
★ Final term past paper

In a CFG the nonterminal that occurs first from the left in the working string, is said to be ________

  1. ALeast Significant nonterminal
  2. BMost Significant nonterminal
  3. CLeft most nonterminal
  4. DLeft most derivate

The first nonterminal from the left is the leftmost nonterminal.

181.
★ Final term past paper

The unit production is

  1. ATerminal --> Terminal
  2. BTerminal --> Non Terminal
  3. CNon terminal --> Terminal
  4. DNon terminal --> Non Terminal

A unit production replaces one nonterminal by one nonterminal.

182.
★ Final term past paper

A ________ operator adds a new letter at the top of STACK

  1. APUSH
  2. BPOP
  3. CREAD
  4. DAPPEND

PUSH puts a letter on top of the stack.

183.
★ Final term past paper

PDA stands for ________

  1. APush and Drop Automaton
  2. BPop and Drop Automaton
  3. CPush Down Automaton
  4. DNone of given options

PDA means pushdown automaton.

184.
★ Final term past paper

In a STACK:

  1. AThe element PUSHed first is POPed first
  2. BThe element PUSHed first is POPed in the last
  3. CThe element PUSHed in last is POPed in last
  4. DNone of given options

A stack is last-in first-out, so the first element pushed is popped last.

185.
★ Final term past paper

Kleene star closure can be defined

  1. AOver any set of string
  2. BOver specific type of string

Kleene closure can be taken of any set of strings.

186.
★ Final term past paper

While finding RE corresponding to TG, we connect the new start state to the old start state by the transition labeled by

  1. Aa
  2. Bb
  3. Cnull string
  4. DNone of the given options

The new start state is joined to old start states by Λ-edges so no input is read.

187.
★ Final term past paper

For a given input, it provides the compliment of Boolean AND output.

  1. ANAND box (NOT AND)
  2. BDELAY box
  3. COR box
  4. DAND box

NAND outputs NOT of AND.

188.
★ Final term past paper

It delays the transmission of signal along the wire by one step (clock pulse).

  1. ANAND box (NOT AND)
  2. BDELAY box
  3. COR box
  4. DAND box

A DELAY box holds the signal for one clock pulse.

189.
★ Final term past paper

For the given input, it provides the Boolean OR output

  1. ANAND box (NOT AND)
  2. BDELAY box
  3. COR box
  4. DAND box

An OR box outputs the Boolean OR.

190.
★ Final term past paper

For the given input, AND box provides the Boolean AND output.

  1. ATrue
  2. BFalse

An AND box outputs the Boolean AND of its inputs.

191.
★ Final term past paper

The current in the wire is indicated by 1 and 0 indicates the absence of the current.

  1. ATrue
  2. BFalse

In the circuit model, 1 means current and 0 means no current.

192.
★ Final term past paper

If L1 and L2 are regular languages ________ is/are also regular language(s).

  1. AL1 + L2
  2. BL1L2
  3. CL1*
  4. DAll of above

Regular languages are closed under union, concatenation and Kleene star.

193.
★ Final term past paper

Let L be a language defined over an alphabet Σ, then the language of strings, defined over Σ, not belonging to L, is called Complement of the language L, denoted by Lc or L'.

  1. ATrue
  2. BFalse

This is the definition of the complement of L.

194.
★ Final term past paper

To describe the complement of a language, it is very important to describe the ________ of that language over which the language is defined.

  1. AAlphabet
  2. BRegular Expression
  3. CString
  4. DWord

The complement is taken relative to Σ*, so the alphabet must be known.

195.
★ Final term past paper

For a certain language L, the complement of Lc is the given language L i.e. (Lc)c = Lc

  1. ATrue
  2. BFalse

(Lc)c equals L, not Lc, so the stated equation is false.

196.
★ Final term past paper

If L is a regular language then, ________ is also a regular language.

  1. ALm
  2. BLs
  3. CLx
  4. DLc

The complement Lc of a regular language is regular.

197.
★ Final term past paper

Converting each of the final states of F to non-final states and old non-final states of F to final states, FA thus obtained will reject every string belonging to L and will accept every string, defined over Σ, not belonging to L. is called

  1. ATransition Graph of L
  2. BRegular expression of L
  3. CComplement of L
  4. DFinite Automata of L

Swapping final and non-final states gives the FA for the complement.

198.
★ Final term past paper

If L1 and L2 are two regular languages, then L1 U L2 is not a regular.

  1. ATrue
  2. BFalse

The union of regular languages is regular.

199.
★ Final term past paper

If L1 and L2 are regular languages, then these can be expressed by the corresponding FAs.

  1. ATrue
  2. BFalse

By Kleene's theorem every regular language has an FA.

200.
★ Final term past paper

L= language of words containing even number of a's. Regular Expression is

  1. A(a+b)*aa(a+b)*
  2. B(b+ab*a)*
  3. Ca+bb*aab*a
  4. D(a+b)*ab(a+b)*

Each block is b or a pair of a's with b's between, so the total number of a's is even.

201.
★ Final term past paper

Let L be any infinite regular language, defined over an alphabet Σ then there exist three strings x, y and z belonging to Σ* such that all the strings of the form xy^n z for n=1,2,3, ... are the words in L. called.

  1. AComplement of L
  2. BPumping Lemma
  3. CKleene's theorem
  4. DNone in given

This statement is the pumping lemma.

202.
★ Final term past paper

Languages are proved to be regular or non regular using pumping lemma.

  1. ATrue
  2. BFalse

The pumping lemma can only show a language is nonregular; some nonregular languages also satisfy it.

203.
★ Final term past paper

If, two strings x and y, defined over Σ, are run over an FA accepting the language L, then x and y are said to belong to the same class if they end in the same state, no matter that state is final or not.

  1. ATrue
  2. BFalse

Classes are defined by the ending state, final or not.

204.
★ Final term past paper

Myhill Nerode theorem is consisting of the followings,

  1. AL partitions Σ* into distinct classes.
  2. BIf L is regular then, L generates finite number of classes.
  3. CIf L generates finite number of classes then L is regular.
  4. DAll of above

The theorem has all three parts.

205.
★ Final term past paper

The language Q is said to be quotient of two regular languages P and R, denoted by ________ if PQ=R.

  1. AR=Q/P
  2. BQ=R/P
  3. CQ=P/R
  4. DP=R/Q

If PQ = R then Q is the quotient R/P.

206.
★ Final term past paper

If two languages R and Q are given, then the prefixes of Q in R denoted by Pref(Q in R).

  1. ATrue
  2. BFalse

Pref(Q in R) is the notation for the prefixes of Q in R.

207.
★ Final term past paper

Let Q = {aa, abaaabb, bbaaaaa, bbbbbbbbbb} and R = {b, bbbb, bbbaaa, bbbaaaaa}. Pref (Q in R) is equal to,

  1. A{b,bbba,bbbaaa}
  2. B{b,bba,bbaaa}
  3. C{ab,bba,bbbaa}
  4. D{b,bba,bbba}

bbba·aa, bbbaaa·aa and b·bbaaaaa are in R, giving {b, bbba, bbbaaa}.

208.
★ Final term past paper

If R is regular language and Q is any language (regular/ non regular), then Pref (Q in R) is ________ .

  1. ANon-regular
  2. BEqual
  3. CRegular
  4. DInfinite

Pref(Q in R) is regular whenever R is regular.

209.
★ Final term past paper

Between the two consecutive joints on a path

  1. AOne character can be pushed and one character can be popped
  2. BAny no. of characters can be pushed and one character can be popped
  3. COne character can be pushed and any no. of characters can be popped
  4. DAny no. of characters can be pushed and any no. of characters can be popped

In conversion form, each row between joints pops one character and may push any number.

210.
★ Final term past paper

There is a problem in deciding whether a state of FA should be marked or not when the language Q is infinite.

  1. ATrue
  2. BFalse

For infinite Q we cannot test every word of Q to decide the marking.

211.
★ Final term past paper

If an effectively solvable problem has answered in yes or no, then this solution is called ________

  1. ADecision procedure
  2. BDecision method
  3. CDecision problem
  4. DDecision making

An algorithm that answers yes or no is a decision procedure.

212.
★ Final term past paper

The following problem(s) ________ is/are called decidable problem(s).

  1. AThe two regular expressions define the same language
  2. BThe two FAs are equivalent
  3. CBoth a and b
  4. DNone of given

Both equivalence questions have decision procedures.

213.
★ Final term past paper

To examine whether a certain FA accepts any words, it is required to seek the paths from ________ state.

  1. AFinal to initial
  2. BFinal to final
  3. CInitial to final
  4. DInitial to initial

The FA accepts some word exactly when a final state is reachable from the initial state.

214.
★ Final term past paper

The CFG is not said to be ambiguous if there exists atleast one word of its language that can be generated by the different production trees,

  1. ATRUE
  2. BFALSE

Such a CFG is ambiguous, so the statement is false.

215.
★ Final term past paper

Proof(Kleene's Theorem Part II) If a TG has more than one start states, then

  1. AIntroduce the new start state
  2. BEliminate the old start state
  3. CReplace the old start state with final state
  4. DReplace the old final state with new start state

A new single start state is added with Λ-edges to the old start states.

216.
★ Final term past paper

Which of the following statement is NOT true about TG?

  1. AThere exists exactly one path for certain string
  2. BThere may exist more than one paths for certain string
  3. CThere may exist no path for certain string
  4. DThere may be no final state

A TG may have several or no paths for a string, so exactly one is not required.

217.
★ Final term past paper

Kleene's theorem states

  1. AAll representations of a regular language are equivalent.
  2. BAll representations of a context free language are equivalent.
  3. CAll representations of a recursive language are equivalent
  4. DFinite Automata are less powerful than Pushdown Automata.

Kleene's theorem says FA, TG and RE describe the same (regular) languages.

218.
★ Final term past paper

A language accepted by an FA is also accepted by

  1. ATG only
  2. BGTG only
  3. CRE only
  4. DAll of the given

By Kleene's theorem the language also has a TG, a GTG and an RE.

219.
★ Final term past paper

Identify FALSE statement:

  1. AEvery Regular Expression be expressed by CFG and every CFG can be expressed by a Regular Expression
  2. BEvery regular expression can be expressed as CFG but every CFG cannot be expressed as a regular expression.
  3. CFor a PDA, there exists a CFG, that represents the same language as represented by PDA.
  4. DNone of the given options

Some CFGs generate nonregular languages, so not every CFG has an RE.

220.
★ Final term 2013

In large FA with thousands of states and millions of directed edges, without an effective procedure it is ________ to find a path from initial to final state.

  1. AAlways easy
  2. BImpossible
  3. Cmay be good
  4. Dalways impossible

The handout says that without an algorithm such a path is impossible to find by inspection.

221.
★ Final term 2013

If there is no final state of two FAs then their ________ also have no ________ state

  1. Ainitial, union
  2. Bfinal, union
  3. Cunion, final
  4. Dunion, initial

A union state is final only if a component is final, so with no final states the union has none.

222.
★ Final term 2013

In the context of Myhill Nerode theorem, for even-even language sigma star can be partitioned into ________ number of classes.

  1. A3
  2. B4
  3. C5
  4. D6

EVEN-EVEN's FA has four states (parities of a's and b's), giving four classes.

223.
★ Final term 2013

The product of two regular languages is ________.

  1. ARegular
  2. Binfinite
  3. Cnon-regular
  4. Dclosure of a regular language

Regular languages are closed under concatenation.

224.
★ Final term 2013

A problem that has decision procedure is called ________ problem.

  1. ARegular language
  2. Bun-decidable
  3. CInfinite
  4. DDecidable

A problem with a decision procedure is decidable.

225.
★ Final term 2013

For a machine with N number of states, the total number of strings to be tested, defined over an alphabet of m letters, is ________.

  1. AN^m + N^(m+1) + N^(m+2) + ... + N^(2m-1)
  2. Bm^N + m^(N+1) + m^(N+2) + ... + m^(2N-1)
  3. CN^m
  4. Dm^N

All strings of lengths N to 2N-1 are tested, and there are m^k strings of length k.

226.
★ Final term 2013

If (L1 ∩ L2c) ∪ (L1c ∩ L2) is regular language that accepts the words which are in L1 but not in L2 or else in L2 but not in L1. The corresponding FA cannot accept any word which is in ________ L1 and L2.

  1. ANot both
  2. BBoth
  3. CAt least in one
  4. DNone of the given options

This symmetric difference excludes words that are in both L1 and L2.

227.
★ Final term past paper

Incase of Myhill Nerode theorem, if a language L partitions sigma star into distinct classes and L is also regular then L generates ________ number of classes.

  1. Ainfinite
  2. Bspecified
  3. Cfinite
  4. Dodd

Myhill-Nerode: a regular language generates finitely many classes.

228.
★ Final term past paper

The production of the form nonterminal → one nonterminal is called the :

  1. ANull production
  2. BNull able production
  3. CUnit production
  4. DNone of the given

Non-terminal → one non-terminal is a unit production.

229.
★ Final term past paper

Let Q and R be expressed by ab*a and (ba)* respectively i.e Q={aa ,aba ,abba ……}and R={Λ,ba, baba,bababa…….}. aba is the only word in Q which can make a word in R, because the words in R don't contain the

  1. ASingle letter
  2. BDouble letter
  3. CString
  4. DNull string

Words of R alternate b and a, so they never contain a double letter such as aa or bb.

230.
★ Final term past paper

Let L be a language defined over an alphabet ∑,then the language of strings , defined over ∑, not belonging to L denoted by LC or L. is called :

  1. ANon regular language of L
  2. BComplement of the language L
  3. CNon of the given
  4. DAll of above

Strings not in L form its complement.

231.
★ Final term past paper

For a certain language L, the complement of Lc is the given language L i.e. (Lc)c = L

  1. ATrue
  2. BFalse

Complementing twice gives L back.

232.
★ Final term past paper

consider a language L defined over an alphabet ∑ if two strings x and y defined over ∑ are run over an FA accepting the language L,then x and y are said to belong to the same ………. if they end in the same …….

  1. AClass ,state
  2. BFinal ,infinite
  3. CRegular ,nonregular
  4. DAll of Above

Strings ending in the same state belong to the same class.

233.
★ Final term past paper

The regular expression defining the language L1 U L2 can be obtained, converting and reducing the previous ------------- into a ------------ as after eliminating states.

  1. AGTG, TG
  2. BFA, GTG
  3. CFA, TG
  4. DTG, RE

The FA is turned into a GTG and states are eliminated to get the RE.

234.
★ Final term past paper

The regular expression thus obtained if contains at least one word then the language is not empty otherwise the language is :

  1. ARegular
  2. BNo regular
  3. CEmpty
  4. DNon of the above

If the RE defines no word, the language is empty.

235.
★ Final term past paper

it is very important to determine which sequences of rows do correspond to possible paths through the:

  1. ACFG
  2. BCFL
  3. CPDA
  4. DTAPE

Only some row sequences of the summary table are real paths through the PDA.

236.
★ Final term past paper

Before the CFG corresponding to the given PDA is determined,the PDA is converted in to the standard form which is called the:

  1. AStandard form
  2. BConversion form
  3. CLeft most derivation
  4. DNone of them

A PDA is first put into conversion form.

237.
★ Final term past paper

……………… is a place where the input letters can be placed until these letters are referred again. It can store as many letters as one can in a long column .

  1. ASTACK
  2. BPOP AND STACK
  3. CPUSHDOWN STACK
  4. DNone of above

The handout defines the PUSHDOWN STACK this way.

238.
★ Final term past paper

Which of the following statement is NOT true:

  1. AFA can be considered to be an NFA
  2. BFA can be considered to be an NFA with null string
  3. CNFA can be considered to be an TG
  4. DTG can be considered to be an NFA

Every FA is an NFA and every NFA is a TG, but a TG (with string labels) is not in general an NFA.

239.
★ Final term past paper

Let FA3 be an FA accepting L1∩L2 then the initial state of FA3 must be correspond to the initial state of………. and initial state of ………

  1. AFA3, FA2
  2. BFA1 , FA2
  3. CFA1,FA3
  4. DNone of the given

The intersection machine starts at the pair of initial states of FA1 and FA2.

240.
★ Final term past paper

FA corresponding to an NFA can be built by introducing a state corresponding to the combination of states, for a letter having

  1. Ano transition at certain state
  2. Bone transition at certain state
  3. Cmore than one transitions at certain state
  4. Dnone of the given options

Several transitions on one letter are merged into one combined state.

241.
★ Final term past paper

A DFA with n states must accept at least one string of length greater than n.

  1. ATrue
  2. BFalse

A DFA may accept a finite language or no word at all.

242.
★ Final term past paper

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

  1. ATrue
  2. BFalse

Concatenation distributes over union.

243.
★ Final term past paper

Choose the right option: (A) In a Mealy machine, the set of letters and the set of output characters must be same. (B) In a Mealy machine, the set of letters and the set of output characters may not be same.

  1. AB only
  2. BA only

Input letters and output characters of a Mealy machine can be different sets.

244.
★ Final term past paper

The following problem(s) ------------- is/are called decidable problem(s). The two regular expressions define the:

  1. Asame language
  2. BThe two FAs are equivalent
  3. CBoth a and b
  4. DNone of given

Both equivalence questions are decidable.

245.
★ Final term past paper

If F accept an ………….. language then there are some words w s.t N ≤ length (w) < 2N :

  1. ARegular
  2. BFinite
  3. CInfinite
  4. DNone of given

An FA with N states accepts an infinite language iff it accepts a word with N ≤ length < 2N.

246.
★ Final term past paper

The values of input (say a & b) does not remain same in one cycle due to

  1. Atape
  2. Bhalt
  3. Cclock pulse
  4. Dstart

Input values change at each clock pulse.

247.
★ Final term past paper

The reverse of the string sbfsbb over { sb, f, b}

  1. A(bsbfsb)
  2. Bbfsbs
  3. Csbbfsb
  4. Dbbfsb

sb·f·sb·b reversed is b·sb·f·sb.

248.
★ Final term past paper

If L1 and L2 are regular languages then which statement is NOT true?

  1. AL1/L2 is always regular
  2. BL1+L2 are always regular
  3. CL1*L2 are always regular
  4. DNone of them

Quotient, union and concatenation of regular languages are all regular.

249.
★ Final term past paper

the moment a final state of ……….. FA is entered ,the possibility of the initial state of ……….. FA will be included as well:

  1. Afirst ,third
  2. Bfirst ,second
  3. Csecond ,third
  4. Dall of above

In the concatenation FA, reaching a final state of the first FA adds the initial state of the second.

250.
★ Final term past paper

An FA has same initial and final state, then it means that it has no final state.

  1. Afalse
  2. Btrue

A state can be both initial and final; the FA then accepts Λ.

251.
★ Final term past paper

If L1 and L2 are two regular languages then L1∩L2 is also :

  1. ARegular
  2. BNone regular
  3. CFinite
  4. DNone infinite

Regular languages are closed under intersection.

252.
★ Final term past paper

For language L defined over {a, b},then L partitions {a, b}* into …… classes:

  1. ADistinct
  2. BAccept
  3. CUnit production
  4. DNone of the above

L partitions Σ* into distinct classes.

253.
★ Final term past paper

If an effectively solvable problem has answer in yes or no ,then this solution is called :

  1. ADecision procedure
  2. BDecidable problem
  3. CSolved able problem
  4. DAll of above

A yes/no algorithm is a decision procedure.

254.
★ Final term past paper

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

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

(a+b)* is (r2)* and (aa+bb)* is (r1)*.

255.
★ Final term past paper

In FA starting state is represented by a sign.

  1. A+
  2. B-
  3. C*
  4. DS

The start state is marked with a minus sign and final states with plus.

256.
★ Final term past paper

The production of the form nonterminal →string of two nonterminals is called a:

  1. Alive production
  2. Bdead production
  3. Ctype of production
  4. Dnone of them

Non-terminal → two non-terminals is a live production.

257.
★ Final term past paper

Converting the given CFG in CNF is the first rule of

  1. ACYK algorithm
  2. BCKY algorithm
  3. CKYC algorithm
  4. DCNK algorithm

The CYK membership algorithm first puts the CFG in CNF.

258.
★ Final term past paper

If a language can be expressed by a regular expression, then its complement cannot be expressed by a regular expression. This statement is:

  1. Atrue
  2. BFalse
  3. CDepends on language
  4. DNone of the given optios

The complement of a regular language is regular, so it has an RE too.

259.
★ Final term past paper

Which statement is true?

  1. AAll words are strings
  2. BAll strings are words
  3. CBoth are always same
  4. DAll letter are string

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

260.
★ Final term past paper

If L1 and L2 are expressed by r1 and r2, respectively then the language expressed by (r1)(r2) will be ________

  1. ARegular
  2. BIr-regular
  3. CUndermined
  4. DSuch language does not exist

The concatenation of two regular expressions is again a regular expression, so its language is regular.

261.
★ Final term past paper

If an FA accepts no string, then language is denoted by ________

  1. A{}
  2. BØ
  3. CBoth {} and Ø
  4. DNull

The empty language can be written either as {} or as Ø.

262.
★ Final term past paper

Which of the following pairs of regular expressions are not equivalent?

  1. A(ab)* and a*b*
  2. Bx(xx)* and (xx)*x
  3. Cx⁺ and x*x⁺
  4. Dx(x)* and (x)*x

a*b* contains aab while (ab)* does not, so they are not equivalent.

263.
★ Final term past paper

Which of the following statement is correct?

  1. AThe length of output string is greater than length of input string in moore machine.
  2. BThe length of output string is greater than length of input string in mealy machine.
  3. CThe length of output string is equal to length of input string in moore machine.
  4. DThe length of output string is less than length of input string in mealy machine.

A Moore machine prints a character in its start state before reading input, so its output is one longer than the input.

264.
★ Final term past paper

Which one of the following statements is INCORRECT:

  1. A(a+b)*aa(a+b)* generates Regular language.
  2. BA language consisting of all strings over Σ={a,b} having equal number of a's and b's is a regular language
  3. CEvery language that can be expressed by FA can also be expressed by RE
  4. DNone of these

EQUAL (equal a's and b's) is nonregular, so calling it regular is incorrect.

265.
★ Final term past paper

Σ = {a,b} then string abbabb has length equal to ________.

  1. AThree
  2. BFour
  3. CFive
  4. DSix

abbabb has six letters, so its length is 6.

266.
★ Final term past paper

If r1 and r2 are regular expressions then (r1)(r2) is a ________.

  1. ARE
  2. BTG
  3. CFA
  4. DGTG

By the recursive definition of regular expressions, the concatenation of two REs is again an RE.

267.
★ Final term past paper

Which of the following is RE for a language defined over Σ={a,b} having words starting with a:

  1. A(a + b)*
  2. Baa(a + b)+
  3. Ca(a + b)*
  4. Da*(a + b)

a(a+b)* puts an a first and allows any string after it.

268.
★ Final term past paper

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

  1. AIncrementing
  2. BComplementing
  3. CDecrementing
  4. DMultiplication

The incrementing (Mealy) machine adds 1 to a binary number and is the basis for a binary adder.

269.
★ Final term past paper

A regular language ________.

  1. AMust be finite
  2. BMust be infinite
  3. CCan be finite or infinite
  4. DComplex Language

Every finite language is regular and many infinite languages (such as a*) are regular too.

270.
★ Final term past paper

If a language can be expressed by a regular expression, then its complement is ________.

  1. ARegular
  2. BNon Regular
  3. CFinite
  4. DInfinite

Regular languages are closed under complement: swap final and non-final states of its FA.

271.
★ Final term past paper

If a given Context Free grammar (CFG) contains a production of the form S→Λ, then ________

  1. AThe corresponding CFL is not empty.
  2. BThe corresponding CFL is empty.
  3. CThe corresponding CFL is not empty if the language is regular
  4. DThe corresponding CFL is empty and non regular.

S→Λ lets the grammar generate the null string, so the language has at least one word.

272.
★ Final term past paper

We can have more than one parse trees for a given string in case of ________ Context Free Grammar (CFG).

  1. Avague
  2. Bambiguous
  3. Chazy
  4. Dsimple

A CFG is ambiguous when some word has more than one derivation (parse) tree.

273.
★ Final term past paper

The language of aⁿbⁿ can be expressed by:

  1. AFA
  2. BTG
  3. CGTG
  4. DPDA

aⁿbⁿ is nonregular, so no FA, TG or GTG accepts it, but it is context free and a PDA accepts it.

274.
★ Final term past paper

Which of the following theorem partitions Σ* into distinct classes?

  1. ADecidability theorem
  2. BMyhill Nerode theorem
  3. CKleen's theorem
  4. DEmptiness theorem

The Myhill-Nerode theorem divides Σ* into classes of indistinguishable strings.

275.
★ Final term past paper

The languages are supposed to be ________ in case of testing pumping lemma.

  1. Acontext free
  2. Birregular
  3. Cboth regular and irregular
  4. Dregular

The pumping lemma proof starts by assuming the language is regular and then reaches a contradiction.

276.
★ Final term past paper

Which of the following states do not have outgoing edges:

  1. AStart
  2. BRead
  3. CPop
  4. DAccept

ACCEPT is a halting state, so no edge leaves it.

277.
★ Final term past paper

"One GTG can generate ________ language".

  1. Amore than one
  2. Bonly one
  3. Conly two
  4. Donly three

A GTG, like any machine, defines exactly one language: the set of words it accepts.

278.
★ Final term past paper

Regular languages are closed under ________

  1. AUnion and Concatenation
  2. BUnion and Division
  3. CUnion and Exponent
  4. DUnion and Factorial

If L1 and L2 are regular then L1 + L2 and L1L2 are regular too.

279.
★ Final term past paper

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

  1. AThree
  2. BFour
  3. COne
  4. DTwo

aAaAbbAa splits uniquely into the letters a, Aa, Abb, Aa, so its length is 4.

280.
★ Final term past paper

In ________ there must be transition for all letters.

  1. ANFA
  2. BFA
  3. CTG
  4. DGTG

In an FA every state must have exactly one outgoing transition for each letter of Σ.

281.
★ Final term past paper

Consider the following Context Free Grammar (CFG) and select the correct choice S → AB A → BSB | a | b B → CC C → SS | b | bb

  1. Aabb is a word in the corresponding CFL.
  2. Babb is not the word of corresponding CFL.
  3. CAny word can be accepted from the corresponding CFL.
  4. Db is a word in the corresponding CFL.

S ⇒ AB ⇒ aB ⇒ aCC ⇒ abC ⇒ abb, so abb is generated; every word has length at least 3, so b is not.

282.
★ Final term past paper

Language of strings having even number of a's is considered to be:

  1. ARegular
  2. BIrrelgular
  3. CIrregular and infinite
  4. DIrregular and finite

An FA with two states (even/odd count of a's) accepts it, so it is regular.

283.
★ Final term past paper

Which of the following refers to an effectively solvable problem having answer in "Yes" or "No"?

  1. ADecision procedure
  2. BLogical problem
  3. CAnalytical problem
  4. DBinary procedure

An effective procedure that always answers a yes/no question is called a decision procedure.

284.
★ Final term past paper

Concatenation of r1 and r2 will be shown as:

  1. Ar1+r2
  2. Br2+r1
  3. Cr2r1
  4. Dr1r2

Concatenation of r1 followed by r2 is written r1r2; + denotes union.

285.
★ Final term past paper

The language of a^n b^n can be expressed by:

  1. AFA
  2. BTG
  3. CGTG
  4. DPDA

a^n b^n is nonregular but context free, so it needs a PDA's stack to count a's.