K.
VARA PRASAD
FLAT ONLINE BIT MID-I
1. There are ________ tuples in finite state machine. 5 (five).
2. Transition function maps. Q * Σ Q
3. Number of states require to accept string ends with 10. 3
4. Extended transition function is________. Q *Σ* Q
5. δ*(q,ya) is equivalent to ______. δ(δ*(q,y),a)
6. String X is accepted by finite automata if .______. δ*(Q0,x) E A
7. Languages of a automata is ________. If it is accepted by automata
8. Language of finite automata is ______. Type 3
9. Finite automata requires minimum _______ number of stacks. 0
10. Number of final state require to accept Φ in minimal finite automata._____ null.
11. How many DFA’s exits with two states over input alphabet {0,1} ? 64
12. The basic limitation of finite automata is that It can’t remember arbitrary large amount
of information.
13. Number of states require to simulate a computer with memory capable of storing ‘3’
words each of length ‘8’. 2^(3*8)
14. FSM with output capability can be used to add two given integer in binary representation.
This is True
15. Left hand side of a production in CFG consists of: Terminals and non-terminals
16. If L is a regular language then, Lc is also a _____ language. Regular
17. 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. none
18. A regular language: Must be infinite
19. The productions of the form nonterminal → one nonterminal, is called _________ Unit
production
20. CFG is stands for Context Free Grammar
21. CSG is stands for Context Sensitive Grammar
22. The language generated by that CFG is regular if _________ semi word and word.
23. The production of the form no terminal → Λ is said to be null production. True
24. The language generated by _____ is called Context Free Language (CFL). CFG.
25. The terminals are designated by _____ letters, while the non-terminals are designated by
_____ letters. Small, capital
26. The symbols that can’t be replaced by anything are called ________ Terminals
27. The symbols that must be replaced by other things are called ______ Non-terminal
28. The grammatical rules are often called ______ Productions
29. If R is regular language and Q is any language (regular/ non regular), then Pref (Q in R) is
________ Regular
30. ___________ states are called the halt states. ACCEPT and REJECT
II year II sem (R20) CSE Page 1
K. VARA PRASAD
31. The part of an FA, where the input string is placed before it is run, is called _______
Input Tape
32. Context free grammar is ______ A regular Expression.
33. The idea of an automation with a stack as auxiliary storage._______ Push down
automata
34. A push down automata is ____ if there is at most one transition applicable to each
configuration. Deterministic.
35. The graphical representation of the transition of finite automata is _____ State diagram.
36. If two sets A and B have no common elements i.e.,(A intersection B) has no element then
such sets are know as? Disjoint
37. The domain D of the relation R is defined as the ______ Set of all First elements of
ordered pair which belongs to R.
38. A language is regular if and only if it is accepted by a finite automata The given
statements is true.
39. A regular grammar is ______ Context Free Grammar.
40. The Context free language closed under ____ union, kleene star, concatenation.
41. Which of the following is not a prefix of abc. bc
(a). e , (b). a, (c). ab, (d). bc
42. ________ is a set of strings Language.
43. ________ is a finite sequence of symbols. String
44. In transition diagram states are represented by Circles
45. Application of finite automata is ________ Lexical analyzer.
46. We formally denote a finite automata by where Q is _______ a finite set of states.
47. A automata is a ______ device. cognitive.
48. A grammar is a ______ device generative.
49. Any given transition graphs have an equivalent _____ NFA, DFA, RE.
50. In transition diagram a state pointed by an arrow represented the ____ state. start
51. NFA stands for non-deterministic finite automata.
52. DFA stands for Deterministic finite automata.
53. Let NFA has a finite number n of states, the DFA will have at most _____ states. 2n
54. Let NFA has a finite number 6 of states, the DFA will have at most _____ states. 64
55. Let maximum number of states in a DFA=128. then its equivalent NFA has ____ 7
56. Let maximum number of states in a DFA=1024. then its equivalent NFA has ____ 10
57. Regular grammar also know as ______ Type 3.
58. Regular grammar is a subset of _______ Type 0,1,2
59. In CFG each production is of the form where A is a variable and is string of symbols from
______ (V,T are variables and terminals). (VUT).
60. A CFG G= _______. (V,T,P,S)
61. Recursive enumerable languages is also know as ______ Type 0
II year II sem (R20) CSE Page 2
K. VARA PRASAD
62. Context sensitive language is also know as _______ Type 1
63. Context free language is also know as _______ Type 2
64. Regular language is also know as ______ Type 3
65. PDA stands for ______ push down automata.
66. W=abcd , then length of w is |w|=______ 4
67. The head can read either from _______ one cell at a time. left-to-right, right-to-left.
68. DFA can recognize _____ only regular language.
69. DFA has: ______ Unique path to the final state.
70. The language generated by a deterministic finite automata is _____ Regular language.
71. Null language:______ {}= Φ.
72. language consisting of the null string is ____ {ε}.
73. Φ* = _____ {ε}
74. If L= {ε}, then L*= ____ {ε}*= {ε}.
75. NFA has : ______ Multiple path to the final state.
76. Extended transition function for DFA ______ δ: Q x Σ Q.
77. Extended transition function for NFA ______ δ: Q x Σ* P(Q).
78. Extended transition function for NFA- ε ______ δ: Q x (Σ U ε) P(Q).
79. Regular Language closed under:_____ complementation, kleene closure, union,
intersection, reverse.
80. Context sensitive language closed under: _____ union, intersection, concatenation.
81. Recursive Language closed under: ______ kleene closure, union, intersection,
complement, concatenation.
82. Recursively Enumerable language closed under: _____ kleene closure, union,
intersection, concatenation.
83. The recognizable property of DFA and NDFA: _____ Must be same.
84. Which one of the following statement is False ____ Context free languages are closed
under intersection.
85. A machine which accepts all the classes of languages is:____ Turing Machnine.
86. Finite state machine _________ recognize palindromes. Cannot.
87. Turing Machine accepts which grammar and which language? Unrestricted and
recursively Enumerable.
88. A FSM can be used to add how many given integers? _____ 3
89. A tree is a graph that is ______ Connected and acyclic.
90. Let ω by any string of length n in {0,1}*. Let L be the set of all substring so ω. What is
the minimum number of states in a NFA that accepts L ____ n+1
91. Top-down theoretical results in computer science use ____ Empirical data.
92. Concatenation of languages are represented as _____ L1 L2.
93. The length of empty string is: ____ 1
94. Find the substring of the given string: abc ______ a, b, c, bc, ab.
II year II sem (R20) CSE Page 3
K. VARA PRASAD
95. The subset construction creates a DFA whose states are ____ Set of NFA States.
96. A DFA is a: ____ Transition system.
97. Finite languages are associated with _____ DFA’s
98. The concept of FSA is much used in this part of the compiler _____ lexical analysis.
99. The part of a FA, where the input string is placed before it is run, is called _____ Input
tape.
100. ∑ is by convention______ finite.
101. How many no of states are required to construct DFA for the given language
L={W€(a,b)*:W has both ab and ba as substrings)_____ 6 states.
102. The grammatical rules are often called___ productions.
103. A dfA IS A___ transition system.
104. Concatenation of lang. are represented as_____- L1L2.
105. Let ∑=(a,b,c,d,e).the number of strings in ∑* of length 4 such that no symbol is used
more than once in a string is___ -120.
106. Which of the following is type 3 language _____ string of odd number of 0’s.
107. In psycholinguistics in particular it has a natural interpretation with reference to ____
speaker-hearer models.
108. All the grammers are represented in how many tuple form? ____ 4.
109. Conversion of a DFA to an NFA _____ requires the subset constructions.
110. Turing machine accepts which grammar and which language?_____ unrestricted and
recursively enumerable.
111. Finte automata are used for pattern matching in text editors for____ compiler lexical
analysis.
112. The length of empty string is____ 1.
113. If A=(0,1) then 2A=? ____ {{},{0},{1},{0,1}}
114. FSM with output capability can be used to add two given integer in binary
representation.this is _____ true.
115. The word formal is formal languages means ______ only form of the string of
symbols is significant.
116. Consider a DFA over ∑=(a,b) accepting all stings which have number of as divisible by
6 and number of bs divisible by 8.what is the minimum number of states that the DFA
will have? ____ 15.
117. Find the prefix of the given string :abacda ____ a,ab,aba,abac,abacd,abacda.
118. What do automata mean? ____ something done automatically.
119. Finite automata requires minimum____number of stacks. ____ 0.
120. Top-down theoretical results in computer science use ______ empirical data.
121. The grammatical rules are often called _____ productions.
122. If ∑*={x} then ∑=? ____ {€,X,XX,XXX}.
123. Complement of a DFA can be obtained by _____ making final states non-final and
II year II sem (R20) CSE Page 4
K. VARA PRASAD
non-final to final.
124. Which of the following conversion is not possible(algorithmically)? _____ non
deterministic PDA to deterministic PDA.
125. A minimum state deterministic finite automation accepting the language
L={W|W€(0,1)*,number of 0s and 1s in W are divisible by 3 and 5,respectively )has
_____ 15 states.
126. A language is regular if and only if ____ accepted by DFA.
127. The subset construction creates a DFA whose states are ____ set of NFA states.
128. There are ____ tuples in finite state machine 5.
129. FSM with output capability can be used to add two given integers in binary
representation.this is ____ true.
130. All the grammars are represented in how many tuple forms?___ 4
131. The smallest finite automaton which aceepts the lang{X/length id x is divisible by 3}
has ____ 3 states.
132. Which of the following is true?____ every finite subset of non-regular set is regular.
133. Let w be any string of length n in (0,1)*.let L be the set of all substrings so w.what is
the mimimum number of states in a non-deterministic finite automation that accepts
L?____ n+1.
134. The proof that for every NFA there is a DFA that recognaises the same lang is by ___
construction.
135. The behavior of a NFA can be stimulated by DFA ______ always.
136. In our discussion of languages,λ represents ___- a function.
137. Find the concatenation of the given lang L1={0,10,100} L2={0,00,000}____
L1L2={00,000,0000,100,1000,10000,100000}.
138. Given an arbitrary non-deterministic finite automaton {} NFA with n states,the max no
of sates in an equivalent minimization DFA is at least _____ 2n.
139. The terminals are designed by _______ letters,while the non-terminals are designated
by______ small,capital.
140. The set of all strings over the alphabet ∑={a,b} (including €) is denoted by ____
(a+b)*.
141. A tree is a graph that is ______ connected and acyclic.
142. Two sets have the same cardinality iff there is a _____ between them. bijection.
143. FSM with output capability can be used to add two given integer in binary
representation.this is _____ true.
144. FSM can recognize ______ only regular grammar.
145. If A=aab then A2=? _____ aaaabb.
146. Which takes a sample of the sentence of a languages as input ,its output is a grammar
which is in some way adequate for the language. _____ grammatical inference
procedures.
II year II sem (R20) CSE Page 5
K. VARA PRASAD
147. Which one of the following statement is false/ _____ context free grammar are
closed under intersections.
148. Grammatical rules which involve the meaning of words are called _____ semantics.
149. An FSM can be used to add how many given integers? _____ 3
150. Number of satates require to simulate a computer with memory capable of string 3’
words each of length 8’_____ 2^(3*8).
151. The symbols that must be replaced by other things are called _______ non terminals.
152. A machine which accepts all the clases of languages is ____ turing machine.
153. The main difference b/w DFA and NFA.____ in DFA,from given state,there cant be
any alphabet leading to two different states.
154. DFAs are used to construct ______ lexical analyzers.
155. The set of natural numbers is ____ finite.
156. Consider the language L=(111+111111)*.the minimum number of states is any DFA
accepting this lang is ______ 9.
157. The length of empty string is. ____ 1.
158. A graph is defined by _____ a set of vertices and a set of edges.
159. A formal grammar is a ______for rewriting strings set of rules.
160. Computing is traditionally viewed as ____ the execution of algorithms.
161. The major problem in the earliest computers was _____ to display mathematical
formulae.
162. According to Chomsky hierarchy all the languages are ____ --.type3.
163. Let A=(0,1).the number of possible stings of length n that can be formed by the
elements of the set A is _____ n2
164. Predicates are ____ functions that return the truth values.
165. What do automata mean ?____ something done automatically.
166. For a given input,it provides the compliment of Boolean AND output _____ NAND
box(NOT AND).
167. Which of the following is true? _____ (0+1)*01(0+1)*+1*0*=(0+1)*
168. A language represented by an non deterministic finite state automata is ____ regualr
language.
II year II sem (R20) CSE Page 6
