Type Here to Get Search Results !

# Formal Languages And Automation Theory MCQs With Answers - Set I

0

Formal Languages And Automation Theory MCQs

Set I

Q1. Finite state machine is __________ tuple machine.

a) 4

b) 5

c) 6

d) unlimited

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

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=Ã˜

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

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

d) None of the mentioned

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!

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

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