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
