**Formal Languages And Automation Theory MCQs **

**Set I**

**Q1. Finite state machine is __________ tuple machine.
**

**a)** 4

**b)** 5 ✔

**c)** 6

**d)** unlimited

**Answer is b)** 5 **Explanation : ** A finite-state machine is formally defined as a 5-tuple (Q, I, Z, ∂, W) such that: Q = finite set of states. I = finite set of input symbols.

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

**a)** Input alphabet

**b)** Transition function

**c)** Output Alphabet ✔

**d)** Initial State

**Answer is c)** Output Alphabet **Explanation : ** A FA can be represented as FA= (Q, ∑, Î´, q0, F) where Q=Finite Set of States, ∑=Finite Input Alphabet, Î´=Transition Function, q0=Initial State, F=Final/Acceptance State).

**Q3. Given: ∑= {a, b}
L= {xÏµ∑*|x is a string combination}
∑4 represents which among the following?**

**a)** {aa, ab, ba, bb}

**b)** {aaaa, abab, Îµ, abaa, aabb} ✔

**c)** {aaa, aab, aba, bbb}

**d)** All of the mentioned

**Answer is b)** {aaaa, abab, Îµ, abaa, aabb} **Explanation : ** ∑* represents any combination of the given set while ∑x represents the set of combinations with length x where x Ïµ I.

**Q4. The following grammar
G = (N, T, P, S)
N = {S, A, B}
T = {a, b, c}
P : S ? aSa
S ? aAa
A ? bB
B ? bB
B ? c 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 is b)** is type 2 but not type 3 **Explanation : ** For explanation Join the discussion below

**Q5. Let L denotes the language generated by the grammar S – OSO/00. Which of the following is true? (GATE CS 2000)
**

**a)** L = O

**b)** L is regular but not O ✔

**c)** L is context free but not regular

**d)** L is not context free

**Answer is b)** L is regular but not O **Explanation : ** Please note that grammar itself is not regular but language L is regular as L can be represented using a regular grammar, for example S -> S00/00.

**Q6. 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? (GATE CS 2000)**

**a)** ScT (S is a subset of T)

**b)** S=T ✔

**c)** TcS (T is a subset of S)

**d)** SnT=Ã˜

**Answer is b)** S=T **Explanation : ** For explanation Join the discussion below

**Q7. Assume the R is a relation on a set A, aRb is partially ordered such that a and b are _____________**

**a)** transitive

**b)** reflexive

**c)** symmetric

**d)** transitive and reflexive ✔

**Answer is d)** transitive and reflexive **Explanation : ** A partially ordered relation refers to one which is Reflexive, Transitive and Antisymmetric.

**Q8. The minimum number of states required to recognize an octal number divisible by 3 are/is
**

**a)** 1

**b)** 3 ✔

**c)** 5

**d)** 7

**Answer is b)** 3 **Explanation : ** According to the question, minimum of 3 states are required to recognize an octal number divisible by 3.

**Q9. Consider the following two statements:
S1: { 0^2n |n >= l} is a regular language
S2: { 0^m 0^n 0^(m+n) l m >= 1 and n >= 2} is a regular language
Which of the following statements is correct? (GATE CS 2001) **

**a)** Only S1 is correct

**b)** Only S2 is correct

**c)** Both S1 and S2 are correct ✔

**d)** None of S1 and S2 is correct

**Answer is c)** Both S1 and S2 are correct **Explanation : ** S1 can be written as (00)^n where n >= 1. And S2 can be written as (00)^(m+n) where m >=2 and n >= 1. S2 can be further reduced to (00)^x where x >= 3.
We can easily write regular grammars for both S1 and S2.

G1 -> G100/00 (For S1)

G2 -> G200/000000 (For S2)

**Q10. Transition function of DFA machine maps.**

**a)** Î£ x Q -> Î£

**b)** Q x Q -> Î£

**c)** Î£ x Î£ -> Q

**d)** Q x Î£ -> Q ✔

**Answer is d)** Q x Î£ -> Q **Explanation : ** For explanation Join the discussion below

**Q11. If an Infinite language is passed to Machine M, the subsidiary which gives a finite solution to the infinite input tape is ______________ **

**a)** Compiler ✔

**b)** Interpreter

**c)** Loader and Linkers

**d)** None of the mentioned

**Answer is a)** Compiler **Explanation : ** A Compiler is used to give a finite solution to an infinite phenomenon. Example of an infinite phenomenon is Language C, etc.

**Q12. Given an arbitrary non-deterministic finite automaton (NFA) with N states, the maximum number of states in an equivalent minimized DFA is at least. (GATE CS 2001)
**

**a)** N^2

**b)** 2^N ✔

**c)** 2N

**d)** N!

**Answer is b)** 2^N **Explanation : ** For explanation Join the discussion below

**Q13. The non- Kleene Star operation accepts the following string of finite length over set A = {0,1} | where string s contains even number of 0 and 1
**

**a)** 01,0011,010101

**b)** 0011,11001100 ✔

**c)** Îµ,0011,11001100

**d)** Îµ,0011,11001100

**Answer is b)** 0011,11001100 **Explanation : ** The Kleene star of A, denoted by A*, is the set of all strings obtained by concatenating zero or more strings from A.

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

**a)** Union

**b)** Concatenation

**c)** Kleene*

**d)** All of the mentioned ✔

**Answer is d)** All of the mentioned **Explanation : ** Union, Intersection, Concatenation, Kleene*, Reverse are all the closure properties of Regular Language.

**Q15. Which of the following statements is true? (GATE CS 2001)**

**a)** If a language is context free it can always be accepted by a deterministic push-down automaton

**b)** The union of two context free languages is context free ✔

**c)** The intersection of two context free languages is context free

**d)** The complement of a context free language is context free

**Answer is b)** The union of two context free languages is context free **Explanation : ** Context-free languages are closed under the following operations. That is, if L and P are context-free languages and D is a regular language, the following languages are context-free as well:

• the Kleene star L * of L

• the image Ã˜(L) of L under a homomorphism Ã˜

• the concatenation of L and P

• the union of L and P

• the intersection of L with a regular language D (L n D).

Context-free languages are not closed under complement, intersection, or difference.

**If you have any doubts join the discussion below ,our Moderator will reply to your Queries**

#### Recommended MCQs

Formal Languages And Automation Theory MCQs With Answers - Set II

Formal Languages And Automation Theory MCQs With Answers - Set III

Formal Languages And Automation Theory MCQs With Answers - Set IV

Formal Languages And Automation Theory MCQs With Answers - Set V

Formal Languages And Automation Theory MCQs With Answers - Set VII

Formal Languages And Automation Theory MCQs With Answers - Set VII

Java MCQs with Answers Set III

Informatica MCQs with Answers Set I

Informatica MCQs with Answers Set II

Informatica MCQs with Answers Set III

Informatica MCQs with Answers Set IV

Informatica MCQs with Answers Set V

Informatica MCQs with Answers Set VI

Computer Organization and Architecture MCQs with Answers Set I

Computer Organization and Architecture MCQs with Answers Set II

Computer Organization and Architecture MCQs with Answers Set III

**If you have any doubts join the discussion below ,our Moderator will reply to your Queries**