**1. Σ = {a,b} Productions**

**S→XaaX **

**X→aX**

**X→bX**

**X→Λ**

**This grammar defines the language expressed by___________**

a. (a+b)aa(a+b)aa

b. (a+b)aba+b)

c. (a+b)aa(a+b)

d. (a+b)a(a+b)a

Correct Answer: __c__

**2. “CFG” stands for _________**

a. Context Finite Grammar

b. Context Free Grammar

c. Context Free Graph

d. Context Finite Graph

Correct Answer: __b__

**3. ___________ states are called the halt states.**

a. ACCEPT and REJECT

b. ACCEPT and READ

c. ACCEPT AND START

d. ACCEPT AND WRITE

Correct Answer: __a__

**4. _____________ is obviously infinite language.**

a. FACTORIAL

b. PALINDROME

c. EQUAL-EQUAL

d. EVEN-EVEN

Correct Answer: __b__

**5. A binary string is divisible by 4 if and only if it ends with:**

a. 1100

b. 11

c. 100

d. 1000

Correct Answer: __c__

**6. A deterministic turing machine is:**

a. unambiguous turing machine

b. Ambiguous turing machine

c. non-deterministic

d. None

Correct Answer: __a__

**7. A PDA machine configuration (p, w, y) can be correctly represented as:**

a. (current state, unprocessed input, stack content)

b. (unprocessed input, stack content, current state)

c. (current state, stack content, unprocessed input)

d. None

Correct Answer: __a__

**8. A regular language over an alphabet ∑ is one that cannot be obtained from the basic languages using the operation**

a. Kleene*

b. All of the mentioned

c. Union

d. Concatenation

Correct Answer: __b__

**9. A->aAa|bAb|a|b|e**

**Which among the following is the correct option for the given production?**

a. Left most derivation

b. Right most derivation

c. Recursive inference

d. None

Correct Answer: __a__

**10. Complement of a DFA can be obtained by**

a. making starting state as final state.

b. no trival method.

c. make final as a starting state.

d. making final states non-final and non-final to final.

Correct Answer: __d__

**11. For a DFA accepting binary numbers whose decimal equivalent is divisible by 4, what are all the possible remainders?**

a. 0,2

b. 0,2,4

c. 0,1,2,3

d. 0

Correct Answer: __c__

**12. Given grammar G:**

**S-> A| B| C**

**A-> aAa| B**

**B-> bB|bb**

**C->aCaa|D**

**D->baD|abD|aa**

**Eliminate e and unit productions and state the number of variables left?**

a. 3

b. 2

c. 5

d. 4

Correct Answer: __c__

**13. If L is a regular language then, ——— is also a regular language.**

a. Ls

b. Lm

c. Lx

d. L’

Correct Answer: __d__

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

a. L1 + L2

b. L1

c. L1L2

d. All of above

Correct Answer: __d__

**15. If L1 and L2 are regular sets then intersection of these two will be**

a. Regular

b. Non Regular

c. Recursive

d. Non Recursive

Correct Answer: __a__

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

a. FALSE

b. True

c.

d.

Correct Answer: __a__

**17. If L1 is regular L2 is unknown but L1-L2 is regular ,then L2 must be**

a. Regular

b. Empty set

c. Decidable

d. CFG

Correct Answer: __a__

**18. In NFA, this very state is like dead-end non final state:**

a. DISTINCT

b. START

c. REJECT

d. ACCEPT

Correct Answer: __c__

**19. Kleene’s theorem states**

**Select correct option:**

a. All representations of a context free language are equivalent.

b.

c. All representations of a regular language are equivalent.

d. Finite Automata are less powerful than Pushdown Automata.

Correct Answer: __d__

**20. Language of finite automata is.**

a. Type 1

b. Type 2

c. Type 3

d. Type 0

Correct Answer: __c__

**21. Languages of a automata is**

a. If it is accepted by automata

b. If it halts

c. If automata touch final state in its life time

d. All language are language of automata

Correct Answer: __a__

**22. Let ∑= {a, b, …. z} and A = {Hello, World}, B= {Input, Output}, then (A*∩B) U (B*∩A) can be represented as:**

a. {Hello, World, ε}

b. {Hello, World, Input, Output, ε}

c. {}

d. {Input, Output, ε}

Correct Answer: __c__

**23. Let FA3 be an FA corresponding to FA1+FA2, then the initial state of FA3 must correspond to the initial state of**

**Select correct option:**

a. FA1 and FA2

b. FA1 or FA2

c. FA2 only

d. FA1 only

Correct Answer: __b__

**24. Let G=(V, T, P, S) be a CFG such that _____________. Then there exists an equivalent grammar G’ having no e productions.**

a. e ∈ L(G)

b. w ∉ L(G)

c. w ∈ L(G)

d. e ∉ L(G)

Correct Answer: __d__

**25. Let h(0)=ab; h(1)=e**

**Let L={abab,baba}**

**h-1(L)= the language of two zeroes and any number of one’s.**

**The given example belongs to which of the following?**

a. Inverse Homomorphism

b. Homomorphism

c. none

d.

Correct Answer: __a__

**26. 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’.**

a. True

b. FALSE

c.

d.

Correct Answer: __a__

**27. NFA, in its name has ’non-deterministic’ because of :**

a. The choice of path is non-deterministic

b. The state to be transited next is non-deterministic

c. The result is undetermined

d. All of the mentioned

Correct Answer: __a__

**28. Number of final state require to accept Φ in minimal finite automata.**

a. 2

b. 3

c. None of the mentioned

d. 1

Correct Answer: __c__

**29. Number of states require to accept string ends with 10.**

a. can’t be represented.

b. 3

c. 2

d. 1

Correct Answer: __b__

**30. Predict the number of transitions required to automate the following language using only 3 states:**

**L= {w | w ends with 00}**

a. 4

b. 5

c. 3

d. 2

Correct Answer: __c__

**31. The Grammar can be defined as: G=(V, ∑, p, S) In the given definition, what does S represents?**

a. Starting Variable

b. Sensitive Grammar

c. Accepting State

d. None of these

Correct Answer: __a__

**32. The grammatical rules are often called_____________**

a. Productions

b. Terminals

c. Non-terminals

d. All of above

Correct Answer: __a__

**33. 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.**

a. a(a+b)a(a+b)(a+b)ab

b. (a+b)aba(a+b)

c. baba(a+b)

d. NONE

Correct Answer: __d__

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

a. FALSE

b. True

c.

d.

Correct Answer: __a__

**35. The maximum number of transition which can be performed over a state in a DFA?**

**∑= {a, b, c}**

a. 2

b. 4

c. 3

d. 1

Correct Answer: __c__

**36. The productions of the form nonterminal → one nonterminal, is called _________**

a. Unit production

b. Null production

c. Null able production

d. None

Correct Answer: __a__

**37. The symbols that can’t be replaced by anything are called —————–**

a. Non-terminals

b. Productions

c. Terminals

d. All of above

Correct Answer: __a__

**38. The symbols that must be replaced by other things are called __________**

a. Terminals

b. Productions

c. Non-terminals

d. All of above

Correct Answer: __a__

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

a. Capital, bold

b. Capital, small

c. Small, bold

d. Small, capital

Correct Answer: __d__

**40. The transition a Push down automaton makes is additionally dependent upon the:**

a. Stack

b. Input tape

c. terminals

d. None

Correct Answer: __a__

**41. There are ________ tuples in finite state machine.**

a. 6

b. unlimited

c. 5

d. 4

Correct Answer: __c__

**42. What is the output for the given language?**

**Language: A set of strings over ∑= {a, b} is taken as input and it prints 1 as an output “for every occurrence of a, b as its substring. (INPUT: abaaab)**

a. 0111010

b. 0010000

c. 0010001

d. 0101010

Correct Answer: __c__

**43. Which among the following is not notated as infinite language?**

a. L={ab}*

b. Factorial

c. Palindrome

d. Reverse

Correct Answer: __b__

**44. Which of the following can accept even palindrome over {a,b}**

a. NDFA

b. Push down Automata

c. Turing Machine

d. All

Correct Answer: __a__

**45. Which of the following does not obey pumping lemma for context free languages ?**

a. Unrestricted languages

b. Finite Languages

c. Context free languages

d. None

Correct Answer: __a__

**46. Which of the following is a correct statement?**

a. Mealy machine has accepting states

b. We can convert Mealy to Moore but not vice versa

c. All oh the mentioned

d. Moore machine has no accepting states

Correct Answer: __d__

**47. Which of the following is a not a part of 5-tuple finite automata?**

a. Initial State

b. Output Alphabet

c. Transition function

d. Input alphabet

Correct Answer: __b__

**48. Which of the following is analogous to the following?**

**:NFA and NPDA**

a. Regular language and Context Free language

b. Context free language and Context Sensitive language

c. Regular language and Context Sensitive language

d. None

Correct Answer: __a__

**49. Which of the following regular expression allows strings on {a,b}* with length n where n is a multiple of 4.**

a. ((a+b)(a+b)(a+b)(a+b))*

b. (bbbb+aaaa)*

c. (a+b+ab+ba+aa+bb+aba+bab+abab+baba)*

d. None

Correct Answer: __a__

**50. Which of the following relates to Chomsky hierarchy?**

a. Regular<CFL<CSL<Unrestricted

b. CFL<CSL<Unrestricted<Regular

c. CSL<Unrestricted<CF<Regular

d. None

Correct Answer: __a__