Deck 2: Formal Languages and Automata Theory: Part B

Question 1

Which of the following denotes Chomskianhiearchy?

A)REG ? CFL ? CSL ? type0
B)CFL ? REG ? type0 ? CSL
C)CSL ? type0 ? REG ? CFL
D)CSL ? CFL ? REG ? type0

Answer 1

REG ? CFL ? CSL ? type0

Question 2

The concept of FSA is much used in this part of the compiler

A)Lexical analysis
B)Parser
C)Code generation
D)Code optimization

Answer 2

Lexical analysis

Question 3

The following grammar G = (N, T, P, S)**spaceN = {S, A, B, C, D, E}**spaceT = {a, b, c}**spaceP : S ? aAB**spaceAB ? CD**spaceCD ? CE**spaceC ? aC**spaceC ? b**spacebE ? bc is

A)is type 3
B)is type 2 but not type 3
C)is type 1 but not type 2
D)is type 0 but not type 1

Answer 3

is type 1 but not type 2

Question 4

The following CFG is in S ? aBB**spaceB ? bAA**spaceA ? a**spaceB ? b

A)Chomsky normal form but not strong Chomsky normal form
B)Weak Chomsky normal form but not Chomsky normal form
C)Strong Chomsky normal form
D)Greibach normal form

Question 5

Which of the following statements is wrong?

A)The regular sets are closed under intersection
B)The class of regular sets is closed under substitution
C)The class of regular sets is closed under homomorphism
D)Context Sensitive Grammar(CSG) can be recognized by Finite State Machine

Question 6

Context free grammar is not closed under

A)Product operation
B)Union
C)Complementation
D)kleene star

Question 7

Let the class of language accepted by finite state machine be L₁ and the class of languages represented by regular expressions be L₂ then

A) L₁
B) L₁>=L₂
C) L₁ U L₂ = .*
D) L₁=L₂

Question 8

Which of the following statement is wrong?

A)Any regular language has an equivalent context-free grammar.
B)Some non-regular languages can't be generated by any context-free grammar
C)Intersection of context free language and a regular language is always context-free
D)All languages can be generated by context- free grammar

Question 9

Grammar that produce more than one Parse tree for same sentence is:

A)Ambiguous
B)Unambiguous
C)Complementation
D)Concatenation

Question 10

The language accepted by a Push down Automata:

A)Type 0
B)Type 1
C)Type 2
D)Type 3

Question 11

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

A)START or READ
B)POP or REJECT
C)READ or POP
D)PUSH or POP

Question 12

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 :

A)Non regular language of L
B)Complement of the language L
C)None of the given
D)All of above

Question 13

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:

A)String
B)Regular language
C)Null string
D)None of the above

Question 14

Let L={w (0 + 1)* w has even number of 1s}, i.e. L is the set of all bit strings with even number of 1s. Which one of the regular expression below represents L?

A)(0*10*1)*
B)0*(10*10*)*
C)0*(10*1*)*0*
D)0*1(10*1)*10*

Question 15

Consider the following Finite State Automaton The language accepted by this automaton is given by the regular expression

A)b*ab*ab*ab
B)(a+b)*
C)b*a(a+b)*
D)b*ab*ab

Question 16

Let L₁ be a recursive language. Let L₂ and L₃ be languages that are recursively enumerable but not recursive. Which of the following statements is not necessarily true?

A)L₂- L₁ is recursively enumerable
B) L₁-L₃ is recursively enumerable
C)L₂ intersection L₁ is recursively enumerable
D)L₂ union L₁ is recursively enumerable

Question 17

Let L denotes the language generated by the grammar S - OSO/00. Which of the following is true?

A)L = O
B)L is regular but not O
C)L is context free but not regular
D)L is not context free

Question 18

Let S and T be language over ={a,b} represented by the regular expressions (a+b*)* and (a+b)*, respectively. Which of the following is true?

A)ScT (S is a subset of T)
B)TcS (T is a subset of S)
C)S=T
D)SnT=Ø

Question 19

Which of the following pairs have DIFFERENT expressive power?

A)Deterministic finite automata (DFA) and Non-Deterministic finite automata(NFA)
B)Deterministic push down automata (DPDA) and Non-deterministic pushdown automata
C)Deterministic single-tape Turing machine and Non-deterministic single-tape Turing Machine
D)Single-tape Turing machine and multi-tape Turing machine

Question 20

Match all items in Group 1 with correct options from those given in Group 2. List I List II**spaceP. Regular Expression
1) Syntax analysis**spaceQ. Push down automata
2) Code Generation**spaceR. Dataflow analysis
3) Lexical analysis**spaceS. Register allocation
4) Code optimization

A)P-4, Q-1, R-2, S-3
B)P-3, Q-1, R-4, S-2
C)P-3, Q-4, R-1, S-2
D)P-2, Q-1, R-4, S-3

Question 21

A minimum state deterministic finite automation accepting the language L = {W W € {0,1}* , number of 0's and 1's in W are divisible by 3 and 5 respectively has

A)15 states
B)11 states
C)10 states
D)9 states

Question 22

Any Language generated by an unrestricted grammar is:

A)Recursive
B)Recursively Enumerable
C)Not Recursive
D)None of the above

Question 23

The Family of recursive language is not closed under which of the following operations:

A)Union
B)Intersection
C)Complementation
D)None of the above.

Question 24

PCP is:

A)Decidable
B)Undecidable
C)Sometimes Decidable
D)None of the

Question 25

If PCP is decidable then MPCP is

A)Decidable
B)Undecidable
C)Can't Say
D)None of the

Question 26

Consider a language L for which there exists a Turing machine , T, that accepts every word in L and either rejects or loops for every word that is not in L. The language L is

A)NP hard
B)NP complete
C)Recursive
D)Recursively enumerable

Question 27

Consider the following statements
I. Recursive languages are closed under complementation
II. Recursively enumerable languages are closed under union
III. Recursively enumerable languages are closed under complementation
Which of the above statement are TRUE?

A)I only
B)I and II
C)I and III
D)II and III

Question 28

Recursively enumerable languages are not closed under

A)Union
B)homomorphism
C)complementation
D)concatenation

Question 29

Which of the following problem is undecidable?

A)Membership problem for CFL
B)Membership problem for regular sets
C)Membership problem for CSL
D)Membership problem for type 0 languages

Question 30

Recursive languages are

A)A proper superset of CFL
B)Always recognized by PDA
C)Are also called type 0 languages
D)Always recognized by FSA

Question 31

Consider the following problem x. Given a Turing machine M over the input alphabet ?, any state q of M. And a word w ? ?*, does the computation of M on w visit the state q? Which of the following statements about x is correct?

A)X is decidable
B)X is undecidable but partially decidable
C)X is undecidable and not even partially decidable
D)X is not a decision problem

Question 32

If a language is denoted by a regular expression L = ( x )* (x y x ), then which of the following is not a legal string within L ?

A)yx
B)xyx
C)x
D)xyxyx

Question 33

Given A = {0,1} and L = A*. If R = (0n1n, n > 0), then language L ? R and R are respectively

A)Regular, regular
B)Not regular, regular
C)Regular, not regular
D)Context free, not regular

Question 34

If L₁ and L₂ are context free language and R a regular set, then which one of the languages below is not necessarily a context free language?

A) L₁ L₂
B) L₁ ? L₂
C) L₁ ? R
D) L₁ ? L₂

Question 35

The logic of pumping lemma is a good example of

A)Pigeon-hole principle
B)Divide-and-conquer technique
C)Recursion
D)Iteration

Question 36

For two regular languages L₁ = (a + b)* a and L₂ = b (a + b ) *, the intersection of L₁ and L₂ is given by

A)(a + b ) * ab
B)ab (a + b ) *
C)a ( a + b ) * b
D)b (a + b ) * a

Question 37

Pumping lemma is generally used for proving that

A)Given grammar is regular
B)Given grammar is not regular
C)Whether two given regular expressions are equivalent or not
D)None of these

Question 38

What is the highest type number which can be applied to the following grammar?
S ->Aa, A -> Ba, B ->abc

A)Type 0
B)Type 1
C)Type 2
D)Type 3

Question 39

Following syntax-directed translation scheme is used with a shift reduction (bottom up) parser that perform the action in braces immediately after a reduction by the corresponding production
A ->aB {print "(1)" A -> c {print "1"),
B ->Ab {print *2"}.
When parser is aaacbbb, then string printed

A)0202021
B)1202020
C)1020202
D)None of these

Question 40

FSM can recognize

A)Any grammar
B)Only CG
C)Both (a) and ( b )
D)Only regular grammar

Question 41

Basic limitation of FSM is that it

A)Cannot remember arbitrary large amount of information
B)Sometimes fails to recognize grammars that are regular
C)Sometimes recognizes grammars are not regular
D)None of these

Question 42

Which of the following are decidable?
1) Whether the intersection of two regular language is infinite.
2) Whether a given context free language is regular.
3) Whether two push down automata accept the same language.
4) Whether a given grammar is context free.

A)1 and 2
B)1 and 4
C)2 and 3
D)2 and 4

Question 43

If L and L¯ are recursively enumerable, then L is

A)Regular
B)Context free
C)Context sensitive
D)Recursive

Question 44

Which of the following problems is undecidable?

A)Membership problem for CFGs
B)Ambiguity problem for CFGs.
C)Finiteness problem for FSAs.
D)Equivalence problem for FSAs.

Question 45

Fred created a new automaton model which is a push down automaton but with two stacks and the added ability of having commands which do not read input tape but which can pop from one stack and push into the other.This new automaton can recognize (choose strongest result)

A)Context Free Language
B)Context sensitive language
C)Regular language
D)Languages recognizable by Turing machine

Question 46

Which of the following statements is/are FALSE?
(1) For every non-deterministic Turing machine, there exists an equivalent deterministic Turing machine.
(2) Turing recognizable languages are closed under union and complementation.
(3) Turing decidable languages are closed under intersection and complementation
(4) Turing recognizable languages are closed under union and intersection.

A)1 and 4 only
B)1 and 3 only
C)2 only
D)3 only

Question 47

Consider a string s over (0+1)*. The number of 0's in s is denoted by no(s) and the number of 1's in s is denoted by n1(s). The language that is not regular is

A)L = {s ? (0+1)* I for every prefix s' of s, I no(s')-n1(s') I ? 2}
B)L = {s ? (0+1)* I no(s) mod 7 = n1(s) mod 5 = 0}
C)L = {s ? (0+1)* I no(s) is a 3 digit prime}
D)L = {s ? (0+1)* I no(s)-n1(s) I ? 4

Question 48

Which one of the following is true regarding FOTRAN?

A)It is a context free language
B)It is a context sensitive language
C)It is a regular language
D)None of the above

Question 49

Which statement is true?

A)The PDA must have one accept state and one reject state
B)The PDA must have one accept state and two reject state
C)The PDA must have two accept state and two reject state
D)There is no reject state in the PDA.

Question 50

TM is more powerful than FSM because

A)The tape movement is confined to one direction
B)It has no finite state control
C)It has the capability to remember arbitrary long sequences of input symbols
D)None of these