This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses on “Finite Automata-Introduction”.
1. Assume the R is a relation on a set A, aRb is partially ordered such that a and b are _____________
a) reflexive
b) transitive
c) symmetric
d) reflexive and transitive
View Answer
Answer: d
Explanation: A partially ordered relation refers to one which is Reflexive, Transitive and Antisymmetric.
2. 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
View Answer
Answer: b
Explanation: The Kleene star of A, denoted by A*, is the set of all strings obtained by concatenating zero or more strings from A.
3. 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
View Answer
Answer: d
Explanation: Union, Intersection, Concatenation, Kleene*, Reverse are all the closure properties of Regular Language.
4. Statement 1: A Finite automata can be represented graphically; Statement 2: The nodes can be its states; Statement 3: The edges or arcs can be used for transitions
Hint: Nodes and Edges are for trees and forests too.
Which of the following make the correct combination?
a) Statement 1 is false but Statement 2 and 3 are correct
b) Statement 1 and 2 are correct while 3 is wrong
c) None of the mentioned statements are correct
d) All of the mentioned
View Answer
Answer: d
Explanation: It is possible to represent a finite automaton graphically, with nodes for states, and arcs for transitions.
5. The minimum number of states required to recognize an octal number divisible by 3 are/is
a) 1
b) 3
c) 5
d) 7
View Answer
Answer: b
Explanation: According to the question, minimum of 3 states are required to recognize an octal number divisible by 3.
6. Which of the following is a not a part of 5-tuple finite automata?
a) Input alphabet
b) Transition function
c) Initial State
d) Output Alphabet
View Answer
Answer: d
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).
7. 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
View Answer
Answer: a
Explanation: A Compiler is used to give a finite solution to an infinite phenomenon. Example of an infinite phenomenon is Language C, etc.
8. The number of elements in the set for the Language L={xϵ(∑r) *|length if x is at most 2} and ∑={0,1} is_________
a) 7
b) 6
c) 8
d) 5
View Answer
Answer: a
Explanation: ∑r= {1,0} and a Kleene* operation would lead to the following set=COUNT{ε,0,1,00,11,01,10} =7.
9. For the following change of state in FA, which of the following codes is an incorrect option?
a) δ (m, 1) =n
b) δ (0, n) =m
c) δ (m,0) =ε
d) s: accept = false; cin >> char;
if char = “0” goto n;
View Answer
Answer: b
Explanation: δ(QX∑) = Q1 is the correct representation of change of state. Here, δ is called the Transition function.
10. 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
View Answer
Answer: b
Explanation: ∑* represents any combination of the given set while ∑x represents the set of combinations with length x where x ϵ I.
Sanfoundry Global Education & Learning Series – Automata Theory.
To practice all areas of Automata Theory, here is complete set of 1000+ Multiple Choice Questions and Answers.
Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!
This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses on “Extended Transition Function”.
1. The number of tuples in an extended Non Deterministic Finite Automaton:
a) 5
b) 6
c) 7
d) 4
View Answer
Answer: a
Explanation: For NFA or extended transition function on NFA, the tuple elements remains same i.e. 5.
2. Choose the correct option for the given statement:
Statement: The DFA shown represents all strings which has 1 at second last position.
a) Correct
b) Incorrect, Incomplete DFA
c) Wrong proposition
d) May be correct
View Answer
Answer: c
Explanation: The given figure is an NFA. The statement contradicts itself.
3. What is wrong in the given definition?
Def: ({q0, q1, q2}, {0,1}, δ, q3, {q3})
a) The definition does not satisfy 5 Tuple definition of NFA
b) There are no transition definition
c) Initial and Final states do not belong to the Graph
d) Initial and final states can’t be same
View Answer
Answer: c
Explanation: q3 does not belong to Q where Q= set of finite states.
4. If δ is the transition function for a given NFA, then we define the δ’ for the DFA accepting the same language would be:
Note: S is a subset of Q and a is a symbol.
a) δ’ (S, a) =Upϵs δ (p, a)
b) δ’ (S, a) =Up≠s δ (p, a)
c) δ’ (S, a) =Upϵs δ(p)
d) δ’ (S) =Up≠s δ(p)
View Answer
Answer: a
Explanation: According to subset construction, equation 1 holds true.
5. What is the relation between DFA and NFA on the basis of computational power?
a) DFA > NFA
b) NFA > DFA
c) Equal
d) Can’t be said
View Answer
Answer: c
Explanation: DFA is said to be a specific case of NFA and for every NFA that exists for a given language, an equivalent DFA also exists.
6. If a string S is accepted by a finite state automaton, S=s1s2s3……sn where siϵ∑ and there exists a sequence of states r0, r1, r2…… rn such that δ(r(i), si+1) =ri+1 for each 0, 1, …n-1, then r(n) is:
a) initial state
b) transition symbol
c) accepting state
d) intermediate state
View Answer
Answer: c
Explanation: r(n) is the final state and accepts the string S after the string being traversed through r(i) other states where I ϵ 01,2…(n-2).
7. According to the given table, compute the number of transitions with 1 as its symbol but not 0:
a) 4
b) 3
c) 2
d) 1
View Answer
Answer: d
Explanation: The transition graph is made and thus the answer can be found.
8. From the given table, δ*(q0, 011) =?
a) {q0}
b) {q1} U {q0, q1, q2}
c) {q2, q1}
d) {q3, q1, q2, q0}
View Answer
Answer: b
Explanation: δ*(q0,011) = Urϵδ*(q0,01) δ (r, 1) = {q0, q1, q2}.
9. Number of times the state q3 or q2 is being a part of extended 6 transition state is
a) 6
b) 5
c) 4
d) 7
View Answer
Answer: a
Explanation: According to the question, presence of q2 or q1 would count so it does and the answer according to the diagram is 6.
10. Predict the missing procedure:
1.Δ(Q0, ε) ={Q0},
2.Δ(Q0, 01) = {Q0, Q1}
3.δ(Q0, 010) =?
a) {Q0, Q1, Q2}
b) {Q0, Q1}
c) {Q0, Q2}
d) {Q1, Q2}
View Answer
Answer: c
Explanation: According to given table and extended transition state implementation, we can find the state at which it rests.
Sanfoundry Global Education & Learning Series – Automata Theory.
To practice all areas of Automata Theory, here is complete set of 1000+ Multiple Choice Questions and Answers.
Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!
This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses on “Regular Expression-Introduction”.
1. L is a regular Language if and only If the set of __________ classes of IL is finite.
a) Equivalence
b) Reflexive
c) Myhill
d) Nerode
View Answer
Answer: a
Explanation: According to Myhill Nerode theorem, the corollary proves the given statement correct for equivalence classes.
2. A language can be generated from simple primitive language in a simple way if and only if
a) It is recognized by a device of infinite states
b) It takes no auxiliary memory
c) Both are correct
d) Both are wrong
View Answer
Answer: b
Explanation: A language is regular if and only if it can be accepted by a finite automaton. Secondly, It supports no concept of auxiliary memory as it loses the data as soon as the device is shut down.
3. Which of the following does not represents the given language?
Language: {0,01}
a) 0+01
b) {0} U {01}
c) {0} U {0}{1}
d) {0} ^ {01}
View Answer
Answer: d
Explanation: The given option represents {0, 01} in different forms using set operations and Regular Expressions. The operator like ^, v, etc. are logical operation and they form invalid regular expressions when used.
4. According to the given language, which among the following expressions does it corresponds to?
Language L={xϵ{0,1}|x is of length 4 or less}
a) (0+1+0+1+0+1+0+1)4
b) (0+1)4
c) (01)4
d) (0+1+ε)4
View Answer
Answer: d
Explanation: The extended notation would be (0+1)4 but however, we may allow some or all the factors to be ε. Thus ε needs to be included in the given regular expression.
5. Which among the following looks similar to the given expression?
((0+1). (0+1)) *
a) {xϵ {0,1} *|x is all binary number with even length}
b) {xϵ {0,1} |x is all binary number with even length}
c) {xϵ {0,1} *|x is all binary number with odd length}
d) {xϵ {0,1} |x is all binary number with odd length}
View Answer
Answer: a
Explanation: The given regular expression corresponds to a language of binary strings which is of even length including a length of 0.
6. If R represents a regular language, which of the following represents the Venn-diagram most correctly?
a) An Irregular Set
b) R*
c) R complement
d) R reverse
View Answer
Answer: b
Explanation: The given diagram represents the Kleene operation over the Regular Language R in which the final states become the initial and the initial state becomes final.
7. The given NFA corresponds to which of the following Regular expressions?
a) (0+1) *(00+11) (0+1) *
b) (0+1) *(00+11) *(0+1) *
c) (0+1) *(00+11) (0+1)
d) (0+1) (00+11) (0+1) *
View Answer
Answer: a
Explanation: The transition states shown are the result of breaking down the given regular expression in fragments. For dot operation, we change a state, for union (plus) operation, we diverge into two transitions and for Kleene Operation, we apply a loop.
8. Concatenation Operation refers to which of the following set operations:
a) Union
b) Dot
c) Kleene
d) Two of the options are correct
View Answer
Answer: b
Explanation: Two operands are said to be performing Concatenation operation AB = A•B = {xy: x ∈ A & y ∈ B}.
9. Concatenation of R with Ф outputs:
a) R
b) Ф
c) R.Ф
d) None of the mentioned
View Answer
Answer: b
Explanation: By distributive property (Regular expression identities), we can prove the given identity to be Ф.
10. RR* can be expressed in which of the forms:
a) R+
b) R-
c) R+ U R-
d) R
View Answer
Answer: a
Explanation: RR*=R+ as R+ means the occurrence to be at least once.
Sanfoundry Global Education & Learning Series – Automata Theory.
To practice all areas of Automata Theory, here is complete set of 1000+ Multiple Choice Questions and Answers.
Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!
This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses on “Regular Language & Expression”.
1. How many strings of length less than 4 contains the language described by the regular expression (x+y)*y(a+ab)*?
a) 7
b) 10
c) 12
d) 11
View Answer
Answer: c
Explanation: string of length 0 = Not possible (because y is always present).
string of length 1 = 1 (y)
string of length 2 = 3 (xy,yy,ya)
string of length 3 = 8 (xxy,xyy,yxy,yyy,yaa,yab,xya,yya)
2. Which of the following is true?
a) (01)*0 = 0(10)*
b) (0+1)*0(0+1)*1(0+1) = (0+1)*01(0+1)*
c) (0+1)*01(0+1)*+1*0* = (0+1)*
d) All of the mentioned
View Answer
Answer: d
Explanation: None.
3. A language is regular if and only if
a) accepted by DFA
b) accepted by PDA
c) accepted by LBA
d) accepted by Turing machine
View Answer
Answer: a
Explanation: All of above machine can accept regular language but all string accepted by machine is regular only for DFA.
4. Regular grammar is
a) context free grammar
b) non context free grammar
c) english grammar
d) none of the mentioned
View Answer
Answer: a
Explanation: Regular grammar is subset of context free grammar.
5. Let the class of language accepted by finite state machine be L1 and the class of languages represented by regular expressions be L2 then
a) L1<L2
b) L1>=L2
c) L1 U L2 = .*
d) L1=L2
View Answer
Answer: d
Explanation: Finite state machine and regular expression have same power to express a language.
6. Which of the following is not a regular expression?
a) [(a+b)*-(aa+bb)]*
b) [(0+1)-(0b+a1)*(a+b)]*
c) (01+11+10)*
d) (1+2+0)*(1+2)*
View Answer
Answer: b
Explanation: Except b all are regular expression*.
7. Regular expression are
a) Type 0 language
b) Type 1 language
c) Type 2 language
d) Type 3 language
View Answer
Answer: a
Explanation: According to Chomsky hierarchy .
8. Which of the following is true?
a) Every subset of a regular set is regular
b) Every finite subset of non-regular set is regular
c) The union of two non regular set is not regular
d) Infinite union of finite set is regular
View Answer
Answer: b
Explanation: None.
9. L and ~L are recursive enumerable then L is
a) Regular
b) Context free
c) Context sensitive
d) Recursive
View Answer
Answer: d
Explanation:If L is recursive enumerable and its complement too if and only if L is recursive.
10. Regular expressions are closed under
a) Union
b) Intersection
c) Kleen star
d) All of the mentioned
View Answer
Answer: d
Explanation: According to definition of regular expression.
Sanfoundry Global Education & Learning Series – Automata Theory.
To practice all areas of Automata Theory, here is complete set of 1000+ Multiple Choice Questions and Answers.
Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!
This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses on “Pumping Lemma for Regular Language”.
1. Relate the following statement:
Statement: All sufficiently long words in a regular language can have a middle section of words repeated a number of times to produce a new word which also lies within the same language.
a) Turing Machine
b) Pumping Lemma
c) Arden’s theorem
d) None of the mentioned
View Answer
Answer: b
Explanation: Pumping lemma defines an essential property for every regular language in automata theory. It has certain rules which decide whether a language is regular or not.
2. While applying Pumping lemma over a language, we consider a string w that belong to L and fragment it into _________ parts.
a) 2
b) 5
c) 3
d) 6
View Answer
Answer: c
Explanation: We select a string w such that w=xyz and |y|>0 and other conditions. However, there exists an integer n such that |w|>=n for any wÎL.
3. If we select a string w such that w∈L, and w=xyz. Which of the following portions cannot be an empty string?
a) x
b) y
c) z
d) all of the mentioned
View Answer
Answer: b
Explanation: The lemma says, the portion y in xyz cannot be zero or empty i.e. |y|>0, this condition needs to be fulfilled to check the conclusion condition.
4. Let w= xyz and y refers to the middle portion and |y|>0.What do we call the process of repeating y 0 or more times before checking that they still belong to the language L or not?
a) Generating
b) Pumping
c) Producing
d) None of the mentioned
View Answer
Answer: b
Explanation: The process of repeatation is called pumping and so, pumping is the process we perform before we check whether the pumped string belongs to L or not.
5. There exists a language L. We define a string w such that w∈L and w=xyz and |w| >=n for some constant integer n.What can be the maximum length of the substring xy i.e. |xy|<=?
a) n
b) |y|
c) |x|
d) none of the mentioned
View Answer
Answer: a
Explanation: It is the first conditional statement of the lemma that states that |xy|<=n, i.e. the maximum length of the substring xy in w can be n only.
6. Fill in the blank in terms of p, where p is the maximum string length in L.
Statement: Finite languages trivially satisfy the pumping lemma by having n = ______
a) p*1
b) p+1
c) p-1
d) None of the mentioned
View Answer
Answer: b
Explanation: Finite languages trivially satisfy the pumping lemma by having n equal to the maximum string length in l plus 1.
7. Answer in accordance to the third and last statement in pumping lemma:
For all _______ xyiz ∈L
a) i>0
b) i<0
c) i<=0
d) i>=0
View Answer
Answer: d
Explanation: Suppose L is a regular language . Then there is an integer n so that for any x∈L and |x|>=n, there are strings u,v,w so that
x= uvw
|uv|<=n
|v|>0
for any m>=0, uvmw ∈L.
8. If d is a final state, which of the following is correct according to the given diagram?
a) x=p, y=qr, z=s
b) x=p, z=qrs
c) x=pr, y=r, z=s
d) All of the mentioned
View Answer
Answer: a
Explanation: The FSA accepts the string pqrs. In terms of pumping lemma, the string pqrs is broken into an x portion an a, a y portion qr and a z portion s.
9. Let w be a string and fragmented by three variable x, y, and z as per pumping lemma. What does these variables represent?
a) string count
b) string
c) both (a) and (b)
d) none of the mentioned
View Answer
Answer: a
Explanation: Given: w =xyz. Here, xyz individually represents strings or rather substrings which we compute over conditions to check the regularity of the language.
10. Which of the following one can relate to the given statement:
Statement: If n items are put into m containers, with n>m, then atleast one container must contain more than one item.
a) Pumping lemma
b) Pigeon Hole principle
c) Count principle
d) None of the mentioned
View Answer
Answer: b
Explanation: Pigeon hole principle states the following example: If there exists n=10 pigeons in m=9 holes, then since 10>9, the pigeonhole principle says that at least one hole has more than one pigeon.
Sanfoundry Global Education & Learning Series – Automata Theory.
To practice all areas of Automata Theory, here is complete set of 1000+ Multiple Choice Questions and Answers.
Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!
This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses on “Reversal-Homomorphism and Inverse Homomorphism”.
1. If L is a language, the reversal of the language can be represented as:
a) L’
b) Lc
c) Lr
d) more than one option is correct
View Answer
Answer: c
Explanation: Lr is defined as the reversal of a language. Lr is a set of strings whose reversal is in L.
Example: L={0, 01, 100}
Lr={0, 10, 001}
2. If L is a regular language, ____ is also regular.
a) Lr
b) L’
c) L*
d) All of the mentioned
View Answer
Answer: d
Explanation: Lr, L’, L* i.e. reversal, complementation and kleene all are the closure properties of regular language.
3. If E=F+G;
Er=?
a) Fr+Gr
b) (F+G)r
c) Both (a) and (b)
d) None of the mentioned
View Answer
Answer: a
Explanation: If E is a symbol a, e, or f, then Er=E. Other inductive properties include union of reversals, concatenation and Kleene.
4. If E= FG, Er=?
a) FrGr
b) GrFr
c) Both (a) and (b)
d) None of the mentioned
View Answer
Answer: b
Explanation: If E= FG, Er=GrFr . Example: (01*)R=(1*)R(0)R
5. Simplify the following identity:
E=01*+10*
ER=?
a) (1*0+0*1)
b) (01*10*)R
c) (0*1+10*)
d) All of the mentioned
View Answer
Answer: a
Explanation: 01*+10*
ER=(01*)R+(10*)R=>(1*)R0R+(0*)R1R=>1*0+0*1
6. Which of the following obey the closure properties of Regular language?
a) Homomorphism
b) Inverse Homomorphism
c) Reversal
d) All of the mentioned
View Answer
Answer: d
Explanation: Homomorphism on an aphabet is a function that gives a string for each symbol in that alphabet. Example: h(0)=ab, etc.
7. Let h(L) be a language of regular expression abe*+e(ab)*. Simplify the h(L)
a) (ab)*+eab*
b) abe*+ea*b*
c) (ab)*
d) None of the mentioned
View Answer
Answer:
abe*+e(ab)*(Using the identities e=e*, eE=Ee=E)
=ab+(ab)*=> ab will contain inside (ab)*, thus =>(ab)*.
8. Let h(0)=ab; h(1)=e
Let L={abab,baba}
h-1(L)=_______
a) the language of two one’s and any number of zeroes
b) the language of two zeroes and any number of one’s
c) the language of two zeroes and two one’s
d) none of the mentioned
View Answer
Answer: b
Explanation: h-1(L) is the language with two 0’s and any number of 1’s=>(1*01*01*).
9. While proving Inverse Homomorphism, which of the following steps are needed?
a) Start with a DFA Ain L
b) Construct a DFA B for h-1(L)
c) The set of states, initial and final states should be same.
d) All of the mentioned
View Answer
Answer: d
Explanation: While constructing DFA B, we need to take care of the following:
a) The same set of states
b) The same start state
c) The same final state
d) Input alphabet = the symbols to which homomorphism h applies.
10. 8. 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) Homomorphism
b) Inverse Homomorphism
c) Both (a) and (b)
d) None of the mentioned
View Answer
Answer: b
Explanation: Let h be a homomorphism and L a language whose alphabet is the output language of h.
h-1(L) = {w | h(w) is in L}.
Sanfoundry Global Education & Learning Series – Automata Theory.
To practice all areas of Automata Theory, here is complete set of 1000+ Multiple Choice Questions and Answers.
Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!
This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses on “Context Free Grammar-Derivations and Definitions”.
1. The entity which generate Language is termed as:
a) Automata
b) Tokens
c) Grammar
d) Data
View Answer
Answer: c
Explanation: The entity which accepts a language is termed as Automata while the one which generates it is called Grammar. Tokens are the smallest individual unit of a program.
2. Production Rule: aAb->agb belongs to which of the following category?
a) Regular Language
b) Context free Language
c) Context Sensitive Language
d) Recursively Ennumerable Language
View Answer
Answer: c
Explanation: Context Sensitive Language or Type 1 or Linearly Bounded Non deterministic Language has the production rule where the production is context dependent i.e. aAb->agb.
3. Which of the following statement is false?
a) Context free language is the subset of context sensitive language
b) Regular language is the subset of context sensitive language
c) Recursively ennumerable language is the super set of regular language
d) Context sensitive language is a subset of context free language
View Answer
Answer: d
Explanation: Every regular language can be produced by context free grammar and context free language can be produced by context sensitive grammar and so on.
4. The Grammar can be defined as: G=(V, ∑, p, S)
In the given definition, what does S represents?
a) Accepting State
b) Starting Variable
c) Sensitive Grammar
d) None of these
View Answer
Answer: b
Explanation: G=(V, ∑, p, S), here V=Finite set of variables, ∑= set of terminals, p= finite productions, S= Starting Variable.
5. Which among the following cannot be accepted by a regular grammar?
a) L is a set of numbers divisible by 2
b) L is a set of binary complement
c) L is a set of string with odd number of 0
d) L is a set of 0n1n
View Answer
Answer: d
Explanation: There exists no finite automata to accept the given language i.e. 0n1n. For other options, it is possible to make a dfa or nfa representing the language set.
6. Which of the expression is appropriate?
For production p: a->b where a∈V and b∈_______
a) V
b) S
c) (V+∑)*
d) V+ ∑
View Answer
Answer: c
Explanation: According to the definition, the starting variable can produce another variable or any terminal or a variable which leads to terminal.
7. For S->0S1|e for ∑={0,1}*, which of the following is wrong for the language produced?
a) Non regular language
b) 0n1n | n>=0
c) 0n1n | n>=1
d) None of the mentioned
View Answer
Answer: d
Explanation: L={e, 01, 0011, 000111, ……0n1n }. As epsilon is a part of the set, thus all the options are correct implying none of them to be wrong.
8. The minimum number of productions required to produce a language consisting of palindrome strings over ∑={a,b} is
a) 3
b) 7
c) 5
d) 6
View Answer
Answer: c
Explanation: The grammar which produces a palindrome set can be written as:
S-> aSa | bSb | e | a | b
L={e, a, b, aba, abbbaabbba…..}
9. Which of the following statement is correct?
a) All Regular grammar are context free but not vice versa
b) All context free grammar are regular grammar but not vice versa
c) Regular grammar and context free grammar are the same entity
d) None of the mentioned
View Answer
Answer: a
Explanation: Regular grammar is a subset of context free grammar and thus all regular grammars are context free.
10. Are ambiguous grammar context free?
a) Yes
b) No
View Answer
Answer: a
Explanation: A context free grammar G is ambiguous if there is atleast one string in L(G) which has two or more distinct leftmost derivations.
Sanfoundry Global Education & Learning Series – Automata Theory.
To practice all areas of Automata Theory, here is complete set of 1000+ Multiple Choice Questions and Answers.
Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!
This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses on “Applications – Parsers”.
1. To derive a string using the production rules of a given grammar, we use:
a) Scanning
b) Parsing
c) Derivation
d) All of the mentioned
View Answer
Answer: b
Explanation: Parsing is required to check the acceptability of a string. Further, comes the syntactical phase which is taken care by other phases of compiler.
2. Which of the following parser reaches the root symbol of the tree at last?
a) Top down parser
b) Bottom up parser
c) TOP down and Bottom up parser
d) None of the mentioned
View Answer
Answer: b
Explanation: Bottom up parser starts from the bottom with the string and comes up to the start symbolusing a parse tree or a derivation tree.
3. Left corner parsing methof uses which of the following?
a) Top down parser
b) Bottom up parser
c) TOP down and Bottom up parser
d) None of the mentioned
View Answer
Answer: c
Explanation: It is a hybrid method which works bottom up along the left edges of each subtree, and top down on the rest of the parse tree.
4. Which of the following parser performs top down parsing?
a) LALR parser
b) LL parser
c) Recursive Accent parser
d) None of the mentioned
View Answer
Answer: b
Explanation: Bottom up parsing is done by shift reduce parsers like LALR parsers, Operator precedence parsers, simple precedence parsers, etc.
5. Which of the following is true for shift reduce parsers?
a) Scans and parses the input in one forward pass over the text, without any backup.
b) A shift command advances in the input stream by one symbol
c) LALR parser
d) All of the mentioned
View Answer
Answer: d
Explanation: The mentioned are the correct and proper functions of a shift reduce parsers. The parsing methods are most commonly used for parsing programming languages, etc.
6. State true or false:
Statement: LALR parsers uses tables rather than mutually recursive functions.
a) true
b) false
View Answer
Answer: b
Explanation: It is exactly the opposite case where LALR parsers uses mutually recursive functions instead of tables. It is a simplified version of canonical left to right parser.
7. LALR in LALR parser stands for:
a) Left aligned left right parser
b) Look ahead left to right parser
c) Language Argument left to right parser
d) None of the mentioned
View Answer
Answer:
Explanation: LALR stands for Look ahead left to right parsers. It has more language recognition power than LR(0) parser.
8. Which of the following can be a LALR parser generator?
a) YACC
b) GNU Bison
c) YACC and GNU Bison
d) None of the mentioned
View Answer
Answer: c
Explanation: YACC is a computer code for UNIX operating system which generates a LALR parser. On the other hand GNU Bison or Bison can generate LALR and GLR parsers.
9. Which of the following parsers do not relate to Bottom up parsing?
a) LL parser
b) Recursive descent parser
c) Earley parsers
d) All of the mentioned
View Answer
Answer: d
Explanation: All the following mentioned are top down parsers and begin their operation from the starting symbol.
10. Which of the following is true for a predictive parser?
a) Recursive Descent parser
b) no backtracking
c) Recursive Descent parser and no backtracking
d) None of the mentioned
View Answer
Answer: c
Explanation: Predictive parsing is possible only for the class of LL-grammars, which are the CFG for which there exists some positive integer k that allows a recursive descent parser to decide which production to use by examining only the next k tokens of input.
Sanfoundry Global Education & Learning Series – Automata Theory.
To practice all areas of Automata Theory, here is complete set of 1000+ Multiple Choice Questions and Answers.
Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!
This set of Automata Theory Questions and Answers for Entrance exams focuses on “PDA-Acceptance by Final State”.
1. A push down automaton employs ________ data structure.
a) Queue
b) Linked List
c) Hash Table
d) Stack
View Answer
Answer: d
Explanation: A push down automata uses a stack to carry out its operations. They are more capable than the finite automatons but less than the turing model.
2. State true or false:
Statement: The operations of PDA never work on elements, other than the top.
a) true
b) false
View Answer
Answer: a
Explanation: The term pushdown refers to the fact that the elements are pushed down in the stack and as per the LIFO principle, the operation is always performed on the top element of the stack.
3. Which of the following allows stacked values to be sub-stacks rather than just finite symbols?
a) Push Down Automaton
b) Turing Machine
c) Nested Stack Automaton
d) None of the mentioned
View Answer
Answer: c
Explanation: In computational theory, a nested stack automaton is a finite automaton which makes use of stack containing data which can be additional stacks.
4. A non deterministic two way, nested stack automaton has n-tuple definition. State the value of n.
a) 5
b) 8
c) 4
d) 10
View Answer
Answer: d
Explanation: The 10-tuple can be stated as: NSA= ‹Q,Σ,Γ,δ,q0,Z0,F,[,],]›.
5. Push down automata accepts _________ languages.
a) Type 3
b) Type 2
c) Type 1
d) Type 0
View Answer
Answer: b
Explanation: Push down automata is for Context free languages and they are termed as Type 2 languages according to Chomsky hierarchy.
6. The class of languages not accepted by non deterministic, nonerasing stack automata is _______
a) NSPACE(n2)
b) NL
c) CSL
d) All of the mentioned
View Answer
Answer: d
Explanation: NSPACE or non deterministic space is the computational resource describing the memory space for a non deterministic turing machine.
7. A push down automaton with only symbol allowed on the stack along with fixed symbol.
a) Embedded PDA
b) Nested Stack automata
c) DPDA
d) Counter Automaton
View Answer
Answer: d
Explanation: This class of automata can recognize a set of context free languages like {anbn|n belongs to N}
8. Which of the operations are eligible in PDA?
a) Push
b) Delete
c) Insert
d) Pop
View Answer
Answer: a, d
Explanation: Push and pop are the operations we perform to operate a stack. A stack follows the LIFO principle, which states its rule as: Last In First Out.
9. A string is accepted by a PDA when
a) Stack is empty
b) Acceptance state
c) Both (a) and (b)
d) None of the mentioned
View Answer
Answer: c
Explanation: When we reach the acceptance state and find the stack to be empty, we say, the string has been accepted by the push down automata.
10. The following move of a PDA is on the basis of:
a) Present state
b) Input Symbol
c) Both (a) and (b)
d) None of the mentioned
View Answer
Answer: c
Explanation: The next operation is performed by PDA considering three factors: present state,symbol on the top of the stack and the input symbol.
Sanfoundry Global Education & Learning Series – Automata Theory.
To practice all areas of Automata Theory for Entrance exams, here is complete set of 1000+ Multiple Choice Questions and Answers.
Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!
This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses on “Deterministic PDA”
1. The transition a Push down automaton makes is additionally dependent upon the:
a) stack
b) input tape
c) terminals
d) none of the mentioned
View Answer
Answer: a
Explanation: A PDA is a finite machine which has an additional stack storage. Its transitions are based not only on input and the correct state but also on the stack.
2. 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 of the mentioned
View Answer
Answer: a
Explanation: A machine configuration is an element of K×Σ*×Γ*.
(p,w,γ) = (current state, unprocessed input, stack content).
3. |-* is the __________ closure of |-
a) symmetric and reflexive
b) transitive and reflexive
c) symmetric and transitive
d) none of the mentioned
View Answer
Answer: b
Explanation: A string w is accepted by a PDA if and only if (s,w, e) |-* (f, e, e)
4. With reference of a DPDA, which among the following do we perform from the start state with an empty stack?
a) process the whole string
b) end in final state
c) end with an empty stack
d) all of the mentioned
View Answer
Answer: d
Explanation: The empty stack in the end is our requirement relative to finite state automatons.
5. A DPDA is a PDA in which:
a) No state p has two outgoing transitions
b) More than one state can have two or more outgoing transitions
c) Atleast one state has more than one transitions
d) None of the mentioned
View Answer
Answer: a
Explanation: A Deterministic Push Down Automata is a Push Down Automata in which no state p has two or more transitions.
6. State true or false:
Statement: For every CFL, G, there exists a PDA M such that L(G) = L(M) and vice versa.
a) true
b) false
View Answer
Answer: a
Explanation: There exists two lemma’s such that:
a) Given a grammar G, construct the PDA and show the equivalence
b) Given a PDA, construct a grammar and show the equivalence
7. If the PDA does not stop on an accepting state and the stack is not empty, the string is:
a) rejected
b) goes into loop forever
c) both (a) and (b)
d) none of the mentioned
View Answer
Answer: a
Explanation: To accept a string, PDA needs to halt at an accepting state and with a stack empty, else it is called rejected. Given a PDA M, we can construct a PDA M’ that accepts the same language as M, by both acceptance criteria.
8. A language accepted by Deterministic Push down automata is closed under which of the following?
a) Complement
b) Union
c) Both (a) and (b)
d) None of the mentioned
View Answer
Answer: a
Explanation: Deterministic Context free languages(one accepted by PDA by final state), are drastically different from the context free languages. For example they are closed under complementation and not union.
9. Which of the following is a simulator for non deterministic automata?
a) JFLAP
b) Gedit
c) FAUTO
d) None of the mentioned
View Answer
Answer: a
Explanation: JFLAP is a software for experimenting with formal topics including NFA, NPDA, multi-tape turing machines and L-systems.
10. Finite-state acceptors for the nested words can be:
a) nested word automata
b) push down automata
c) ndfa
d) none of the mentioned
View Answer
Answer: a
Explanation: The linear encodings of languages accepted by finite nested word automata gives the class of ‘visibly pushdown automata’.
Sanfoundry Global Education & Learning Series – Automata Theory.
To practice all areas of Automata Theory, here is complete set of 1000+ Multiple Choice Questions and Answers.
Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!
This set of Automata Theory Assessment Questions and Answers focuses on “CFG-Eliminating Useless Symbols”.
1. Suppose A->xBz and B->y, then the simplified grammar would be:
a) A->xyz
b) A->xBz|xyz
c) A->xBz|B|y
d) none of the mentioned
View Answer
Answer: a
Explanation: For the first step, substitute B in first production as it only produces terminal and remove B production as it has already been utilized.
We get A->xBz|xyz and now, as B has no production, we eliminate the terms which hold the variable B, thus the answer remain A->xyz.
2. Given Grammar: S->A, A->aA, A->e, B->bA
Which among the following productions are Useless productions?
a) S->A
b) A->aA
c) A->e
d) B->bA
View Answer
Answer: d
Explanation: Some derivations are not reachable from the starting variable. As B is not reachable from the starting variable, it is a useless symbol and thus, can be eliminated.
3. Given:
S->…->xAy->…->w
if ____________, then A is useful, else useless symbol.
a) A is a non terminal
b) A is a terminal
c) w Î L
d) w Ë L
View Answer
Answer: c
Explanation: Whatever operation we perform in intermediate stages, if the string produced belongs to the language, A is termed as useful and if not, not a useful variable.
4. Given:
S->aSb
S->e
S-> A
A->aA
B->C
C->D
The ratio of number of useless variables to number of useless production is:
a) 1
b) 3/4
c) 2/3
d) 0
View Answer
Answer: a
Explanation: A, B, C, D are the useless symbols in the given grammar as they never tend to lead to a terminal. The productions S-> A, A->aA, B->C, C->D are also termed as useless production as they will never produce a string to the grammar.
5. Given grammar G:
S->aS|A|C
A->a
B->aa
C->aCb
Find the set of variables thet can produce strings only with the set of terminals.
a) {C}
b) {A,B}
c) {A,B,S}
d) None of the mentioned
View Answer
Answer: c
Explanation: First step: Make a set of variables that directly end up with a terminal
Second step: Modify the set with variables that produce the elements of above
generated set.
The rest variables are termed as useless.
6. Given grammar:
S->aS|A
A->a
B->aa
Find the number of variables reachable from the Starting Variable?
a) 0
b) 1
c) 2
d) None of the mentioned
View Answer
Answer: b
Explanation: Use a dependency graph to find which variable is reachable and which is not.
7. Inorder to simplify a context free grammar, we can skip the following operation:
a) Removal of null production
b) Removal of useless symbols
c) Removal of unit productions
d) None of the mentioned
View Answer
Answer: d
Explanation: Inorder to simplify the grammar all of the process including the removal of null productions, unit productions and useless symbols is necessary.
8. Given a Grammar G:
S->aA
A->a
A->B
B->A
B->bb
Which among the following will be the simplified grammar?
a) S->aA|aB, A->a, B->bb
b) S->aA|aB, A->B, B->bb
c) S->aA|aB, A->a, B->A
d) None of the emntioned
View Answer
Answer: a
Explanation: Step 1: Substitute A->B
Step 2: Remove B->B
Step 3: Substitute B->A
Step 4: Remove Repeated productions
9. Simplify the given grammar:
A-> a| aaA| abBc
B-> abba| b
a) A-> a| aaA| ababbAc| abbc
b) A-> a| aaA| ababbAc| abbc, B-> abba|b
c) A-> a| aaA| abbc, B->abba
d) None of the mentioned
View Answer
Answer: a
Explanation: Using the substitution rules, we can simply eradicate what is useless and thus produce the simplified result i.e. A-> a| aaA| ababbAc| abbc.
10. In context to the process of removing useless symbols, which of the following is correct?
a) We remove the Nullable variables
b) We eliminate the unit productions
c) We eliminate products which yield no terminals
d) All of the mentioned
View Answer
Answer: c
Explanation: In the process of removal of useless symbols, we want to remove productions that can never take part in any derivation.
Sanfoundry Global Education & Learning Series – Automata Theory.
To practice all areas of Automata Theory Assessment Questions, here is complete set of 1000+ Multiple Choice Questions and Answers.
Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!
This set of Automata Theory Questions and Answers for Campus interviews focuses on “Pumping Lemma for Context Free Language”.
1. Which of the following is called Bar-Hillel lemma?
a) Pumping lemma for regular language
b) Pumping lemma for context free languages
c) Pumping lemma for context sensitive languages
d) None of the mentioned
View Answer
Answer: b
Explanation: In automata theory, the pumping lemma for context free languages, also kmown as the Bar-Hillel lemma, represents a property of all context free languages.
2. Which of the expressions correctly is an requirement of the pumping lemma for the context free languages?
a) uvnwxny
b) uvnwnxny
c) uv2nwx2ny
d) All of the mentioned
View Answer
Answer: b
Explanation: Let L be a CFL. Then there is an integer n so that for any u that belong to language L satisfying |t| >=n, there are strings u, v, w, x, y and z satisfying
t=uvwxy
|vx|>0
|vwx|<=n
For any m>=0, uvnwxny ∈ L
3.Let L be a CFL. Then there is an integer n so that for any u that belong to language L satisfying
|t|>=n, there are strings u, v, w, x, y and z satisfying
t=uvwxy.
Let p be the number of variables in CNF form of the context free grammar. The value of n in terms of p :
a) 2p
b) 2p
c) 2p+1
d) p2
View Answer
Answer: c
Explanation: This inequation has been derived from derivation tree for t which must have height at least p+2(It has more than 2p leaf nodes, and therefore its height is >p+1).
4. Which of the following gives a positive result to the pumping lemma restrictions and requirements?
a) {aibici|i>=0}
b) {0i1i|i>=0}
c) {ss|s∈{a,b}*}
d) None of the mentioned
View Answer
Answer: b
Explanation: A positive result to the pumping lemma shows that the language is a CFL and ist contradiction or negative result shows that the given language is not a Context Free language.
5. Using pumping lemma, which of the following cannot be proved as ‘not a CFL’?
a) {aibici|i>=0}
b) {ss|s∈{a,b}*}
c) The set legal C programs
d) None of the mentioned
View Answer
Answer: d
Explanation: There are few rules in C that are context dependent. For example, declaration of a variable before it can be used.
6. State true or false:
Statement: We cannot use Ogden’s lemma when pumping lemma fails.
a) true
b) false
View Answer
Answer: b
Explanation: Although the pumping lemma provides some information about v and x that are pumped, it says little about the location of these substrings in the string t. It can be used whenever the pumping lemma fails. Example: {apbqcrds|p=0 or q=r=s}, etc.
7. Which of the following cannot be filled in the blank below?
Statement: There are CFLs L1 nad L2 so that ___________is not a CFL.
a) L1∩L2
b) L1′
c) L1*
d) None of the mentioned
View Answer
Answer: c
Explanation: A set of context free language is closed under the following operations:
a) Union
b) Concatenation
c) Kleene
8. The pumping lemma is often used to prove that a language is:
a) Context free
b) Not context free
c) Regular
d) None of the mentioned
View Answer
Answer: b
Explanation: The pumping lemma is often used to prove that a given language L is non-context-free, by showing that arbitrarily long strings s are in L that cannot be “pumped” without producing strings outside L.
9. What is the pumping length of string of length x?
a) x+1
b) x
c) x-1
d) x2
View Answer
Answer: a
Explanation: There exists a property of all strings in the language that are of length p, where p is the constant-called the pumping length .For a finite language L, p is equal to the maximum string length in L plus 1.
10. Which of the following does not obey pumping lemma for context free languages ?
a) Finite languages
b) Context free languages
c) Unrestricted languages
d) None of the mentioned
View Answer
Answer: c
Explanation: Finite languages (which are regular hence context free ) obey pumping lemma where as unrestricted languages like recursive languages do not obey pumping lemma for context free languages.
Sanfoundry Global Education & Learning Series – Automata Theory.
To practice all areas of Automata Theory for Campus Interviews, here is complete set of 1000+ Multiple Choice Questions and Answers.
Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!
This set of Automata Theory Interview Questions and Answers for freshers focuses on “Turing Machine – Notation and Transition Diagrams”.
1. A turing machine is a
a) real machine
b) abstract machine
c) hypothetical machine
d) more than one option is correct
View Answer
Answer: d
Explanation: A turing machine is abstract or hypothetical machine thought by mathematician Alan Turing in 1936 capable of simulating any algorithm, however complicated it is.
2. A turing machine operates over:
a) finite memory tape
b) infinite memory tape
c) depends on the algorithm
d) none of the mentioned
View Answer
Answer: b
Explanation: The turing machine operates on an infinite memory tape divided into cells. The machine positions its head over the cell and reads the symbol.
3. Which of the functions are not performed by the turing machine after reading a symbol?
a) writes the symbol
b) moves the tape one cell left/right
c) proceeds with next instruction or halts
d) none of the mentioned
View Answer
Answer: d
Explanation: After the read head reads the symbol from the input tape, it performs the following functions:
a) writes a symbol(some model allow symbol erasure/no writing)
b) moves the tape left or right (some models allows no motion)
c) proceeds with subsequent instruction or goes either into accepting halting state or rejecting halting state.
4. ‘a’ in a-machine is :
a) Alan
b) arbitrary
c) automatic
d) None of the mentioned
View Answer
Answer: c
Explanation: The turing machine was invented by Alan turing in 1936. He named it as a-machine(automatic machine).
5. Which of the problems were not answered when the turing machine was invented?
a) Does a machine exists that can determine whether any arbitrary machine on its tape is circular.
b) Does a machine exists that can determine whether any arbitrary machine on its tape is ever prints a symbol
c) Hilbert Entscheidungs problem
d) None of the mentioned
View Answer
Answer: d
Explanation: Invention of turing machine answered a lot of questions which included problems like decision problem, etc.) . Alan was able to prove the properties of computation using such model.
6. The ability for a system of instructions to simulate a Turing Machine is called _________
a) Turing Completeness
b) Simulation
c) Turing Halting
d) None of the mentioned
View Answer
Answer: a
Explanation: Turing Completeness the ability for a system of instructions to simulate a Turing machine. A programming language that is Turing complete is theoretically capable of expressing all tasks accomplishable by computers; nearly all programming languages are Turing complete.
7. Turing machine can be represented using the following tools:
a) Transition graph
b) Transition table
c) Queue and Input tape
d) All of the mentioned
View Answer
Answer: d
Explanation: We can represent a turing machine, graphically, tabularly and diagramatically.
8. Which of the following is false for an abstract machine?
a) Turing machine
b) theoretical model of computer
c) assumes a discrete time paradigm
d) all of the mentioned
View Answer
Answer: d
Explanation: A n abstract machine also known as abstract computer, is a theoretical model of computer or hardware system in automata theory. Abstraction in computing process usually assumes a discrete time paradigm.
9. Fill in the blank with the most appropriate option.
Statement: In theory of computation, abstract machines are often used in ___________ regarding computability or to analyze the complexity of an algorithm.
a) thought experiments
b) principle
c) hypothesis
d) all of the mentioned
View Answer
Answer: d
Explanation: A thought experiment considers some hypothesis, theory or principle for the purpose of thinking through its consequences.
10. State true or false:
Statement: RAM model allows random access to indexed memory locations.
a) true
b) false
View Answer
Answer: a
Explanation: In computer science, Random access machine is an abstract machine in the general class of register machines. Random access machine should not be confused with Random access memory.
Sanfoundry Global Education & Learning Series – Automata Theory.
To practice all areas of Automata Theory for Interviews, here is complete set of 1000+ Multiple Choice Questions and Answers.
Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!
This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses on “Multitape Turing Machines”.
1. A turing machine with several tapes in known as:
a) Multi-tape turing machine
b) Poly-tape turing maching
c) Universal turing machine
d) All of the mentioned
View Answer
Answer: a
Explanation: A multitape turing machine is an ordinary turing machine with multiple tapes. Each tape has its own head to control the read and write.
2. A multitape turing machine is ________ powerful than a single tape turing machine.
a) more
b) less
c) equal
d) none of the mentioned
View Answer
Answer: a
Explanation: The multitape turing machine model seems much powerful than the single tape model, but any multi tape machine, no matter how many tapes, can be simulated by single taped TM.
3. In what ratio, more computation time is needed to simulate multitape turing machines using single tape turing machines?
a) doubly
b) triple
c) quadratically
d) none of the mentioned
View Answer
Answer: c
Explanation: Thus, multitape turing machines cannot calculate any more functions than single tape machines.
4. Which of the following is true for two stack turing machines?
a) one read only input
b) two storage tapes
c) Both (a) and (b)
d) None of the mentioned
View Answer
Answer: c
Explanation: Two-stack Turing machines have a read-only input and two storage tapes. If a head moves left on either tape a blank is printed on that tape, but one symbol from a “library” can be printed.
5. Which of the following is not a Non deterministic turing machine?
a) Alternating Turing machine
b) Probabalistic Turing machine
c) Read-only turing machine
d) None of the mentioned
View Answer
Answer: c
Explanation: A read only turing machine or 2 way deterministic finite automaton is a class of model of computability that behaves like a turing machine, and can move in both directions across input, except cannot write to its input tape.
6. Which of the turing machines have existential and universal states?
a) Alternating Turing machine
b) Probalistic Turing machine
c) Read-only turing machine
d) None of the mentioned
View Answer
Answer: a
Explanation: ATM is divide into two sets: an existential state is accepting if some transitions leads to an accepting state; an universal state is accepting if every transition leads to an accepting state.
7. Which of the following is false for Quantum Turing machine?
a) Abstract machine
b) Any quantum algorithm can be expressed formally as a particular quantum turing machine
c) Gives a solution to ‘Is a universal quantum computer sufficient’
d) None of the mentioned
View Answer
Answer: c
Explanation: ‘Is a universal quantum computer sufficient’ is one of the unsolved problem from physics.
8. A deterministic turing machine is:
a) ambiguous turing machine
b) unambiguous turing machine
c) non-deterministic
d) none of the mentioned
View Answer
Answer: b
Explanation: A deterministic turing machine is unambiguous and for every input, there is exactly one operation possible. It is a subset of non-deterministic Turing machines.
9. Which of the following is true about Turing’s a-machine?
a) a stands for automatic
b) left ended, right end-infinite
c) finite number of tape symbols were allowed
d) all of the mentioned
View Answer
Answer: d
Explanation: Turings a- machine or automatic machine was left ended,right end infinite.Any of finite number of tape symbols were allowed and the 5 tuples were not in order.
10. Which of the following is a multi tape turing machine?
a) Post turing Machine
b) Wang-B Machine
c) Oblivious turing Machine
d) All of the mentioned
View Answer
Answer: c
Explanation: An oblivious turing machine where movements of various heads are fixed functions of time, independent of the input. Pippenger and Fischer showed that any computation that can be performed by a multi-tape Turing machine in n steps can be performed by an oblivious two-tape Turing machine in O(n log n) steps.
Sanfoundry Global Education & Learning Series – Automata Theory.
To practice all areas of Automata Theory, here is complete set of 1000+ Multiple Choice Questions and Answers.
Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!
This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses on “The Diagonalization Languages”
1. Which of the following technique is used to find whether a natural language isnt recursive ennumerable?
a) Diagonalization
b) Recursive Induction
c) Both (a) and (b)
d) None of the mentioned
View Answer
Answer: a
Explanation: To find a non recursively ennumerable language, we use the technique of diagonalization.
2. Diagonalization can be useful in:
a) To find a non recursively ennumerable language
b) To prove undecidablility of haltig problem
c) Both (a) and (b)
d) None of the mentioned
View Answer
Answer: c
Explanation: Diagonalization is a technique we use for the following operations:
a) To find a non recursively ennumerable language.
b) To prove undecidablility of halting problem.
3. Which of the following are undecidable problems?
a) Determining whether two grammars generate the same language
b) Determining whether a grammar is ambiguous
c) Both (a) and (b)
d) None of the mentioned
View Answer
Answer: c
Explanation: In contrast we can put up an algorithm for checking whether two FA’s are equivalent and this program can be implemented as a program.
4. Which of the following are incorrect options?
a) Informally, problem is a yes/no question about an infinite set of possible instances
b) Formally, a problem is a language
c) Both (a) and (b)
d) None of the mentioned
View Answer
Answer: d
Explanation: Example: Does a graph G has a Hamilton cycle?
=>Each undirected graph is an instance of Hamilton cycle problem.
5. If a problem has an algorithm to answer it, we call it _________
a) decidable
b) solved
c) recognizable
d) none of the mentioned
View Answer
Answer: a
Explanation: An algorithm is a TM that halts on all inputs,accepted or not. Putting other way, decidable problems are recursive languages.
6. Which of the following are decidable problems?
a) Can a particular line of code in a program ever be executed?
b) Do two given CFG’s generate the same language
c) Is a given CFG ambiguous?
d) None of the mentioned
View Answer
Answer: d
Explanation: All of the mentioned problems are undecidable.
7.Which one of the following is true for the given?
A={(M,w)|M is a turing machine that accepts string w}
a) A concrete undecidable problem
b) A is recognizable but not decidable
c) -A is not recognizable
d) All of the mentioned
View Answer
Answer: d
Explanation: We can proof A to be undecidable using the contradiction method.
8. Which of the following are correct statements?
a) TMs that always halt are known as Decidable problems
b) TMs that are guaranteed to halt only on acceptance are recursive ennumerable.
c) Both (a) and (b)
d) None of the mentioned
View Answer
Answer: c
Explanation: There are two types of TMs on the basis of halting: Recursive and Recursively Ennumerable(TM may or may not halt,could loop forever).
9. Statement: If L id R.E., Lc needs to be R.E. Is it correct?
a) Yes
b) No
c) Maybe
d) Cannot predict
View Answer
Answer: b
Explanation: Any recursive ennumerable language is not closed under complementation.
10. Which of the following is true for The Halting problem?
a) It is recursively ennumerable
b) It is undecidable
c) Both (a) and (b)
d) None of the mentioned
View Answer
Answer: c
Explanation: Halting problem: Does a given Turing machine M halt on a given input w?
11. With reference to binary strings, state true or false:
Statement: For any turing machine, the input alphabet is restricted to {0,1}.
a) true
b) false
View Answer
Answer: a
Explanation: When turing machines are coded as Binary strings, we are restricted to take any input alphabet except {0,1}.
12. With reference ti enumeration of binary strings, the conversion of binary strings to integer is possible by treating the resulting string as a base ____ integer.
a) 2
b) 8
c) 16
d) All of the mentioned
View Answer
Answer: a
Explanation: It makes sense to talk about the i-th binary string” and about “the i-th Turing machine. If i makes no sense as a TM, assume the i-th TM accepts nothing.
Sanfoundry Global Education & Learning Series – Automata Theory.
To practice all areas of Automata Theory, here is complete set of 1000+ Multiple Choice Questions and Answers.
Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!
This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses on “Rice’s Theorem, Properties and PCP”.
1. According to the rice’s theorem, If P is a non trivial property, Lp is :
a) infinite
b) decidable
c) undecidable
d) none of the mentioned
View Answer
Answer: c
Explanation: Rice’s theorem states that ‘Any non trivial property about the language recognized by a turing machine is undecidable’.
2. Fill in the blank with reference to Rice’s theorem.
For any non-trivial property of __________ no general or effective method can decide whether an algorithm computes it with that property.
a) partial functions
b) piecewise functions
c) both (a) and (b)
d) none of the mentioned
View Answer
Answer: a
Explanation: A property of partial functions is called trivial if it holds for all partial computable functions or for none, and an effective decision method is called general if it decides correctly for every algorithm.
3. Which of the following is incorrect according to rice theorem?
Let S be a set of language hat is non trivial:
a) there exists a TM that recognizes the language in S
b) there exists a TM that recognizes the language not in S
c) both (a) and (b)
d) none of the mentioned
View Answer
Answer: c
Explanation: According to rice theorem, it is undecidable to determine whether the language recognized by an arbitrary turing machine lies in S.
4. Which of the following set of computable functions are decidable?
a) The class of computable functions that are constant, and its complement
b) The class of indices for computable functions that are total
c) The class of indices for recursively enumerable sets that are cofinite
d) All of the mentioned
View Answer
Answer: d
Explanation: According to Rice’s theorem, if there exists atleast one computable function in a particular class C of computable functions and another computable function not in C then the problem deciding whether a particular program computes a function in C is undecidable.
5. Which of the following statements are undecidable?
For a given Turing Machine M,
a) does M halt on an empty input tape
b) does M halt for anly inputs at all?
c) is L(M) regular? Context free? Turing decidable?
d) all of the mentioned
View Answer
Answer: d
Explanation: All of the following mentioned are immediate results of Rice’s theorem and thus, undecidable.
6. Post Correspondence problem is
a) decidable decision problem
b) undecidable decision problem
c) not a decision problem
d) none of the mentioned
View Answer
Answer: b
Explanation: Post Correspondence problem is an undecidable decision problem that was introduced by Emil Post in 1946. Being simpler than halting problem, it can be used in proofs of undecidability.
7. State true or false:
Statement: The difference between PCP and MPCP is that in MPCP, a solution is required to start with the first string on each list.
a) true
b) false
View Answer
Answer: a
Explanation: The MPCP is : Given lists A and B of K strings ,say A = w1 ,w2, …wk and B= x1, x2,…..xk does there exists a sequence of integers i1,i2,…ir such that w1wi1wi2…..wir = x1xi1xi2…xir?
8. PCP stands for?
a) Post Correspondence Problem
b) Post Corresponding Problem
c) Pre Correspondence problem
d) None of the mentioned
View Answer
Answer: a
Explanation: PCP or Post Correspondence problem is an undecidable decision problem.
9. Can a Modified PCP problem be reduced to PCP?
a) yes
b) no
View Answer
Answer: a
Explanation: Yes, it can be. There exists a theorem and as well as its proof which supports the assertion.
10. Consider three decision problem A, B, C. A is decidable and B is not. Which of the following is a correct option?
a) C is undecidable if C is reducible to B
b) C is undecidable if B is reducible to C
c) C is decidable if A is reducible to C
d) C is decidable if C is reducible to B’s complement.
View Answer
Answer: b
Explanation: As B is undecidable and it can be reduced to C, C is also an undecidable problem.
Sanfoundry Global Education & Learning Series – Automata Theory.
To practice all areas of Automata Theory, here is complete set of 1000+ Multiple Choice Questions and Answers.
Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!
This set of Automata Theory Interview Questions and Answers for Experienced people focuses on “Problem Solvable in Polynomial Time”.
1. If the number of steps required to solve a problem is O(nk), then the problem is said to be solved in:
a) non-polynomial time
b) polynomial time
c) infinite time
d) none of the mentioned
View Answer
Answer: b
Explanation: Most of the operations like addition, subtraction, etc as well as computing functions including powers, square roots and logarithms can be performed in polynomial time. In the given question, n is the complexity of the input and k is some non negative integer.
2. The value of constants like p and e can be calculated in:
a) polynomial time
b) non-polynomial time
c) cannot be calculated
d) none of the mentioned
View Answer
Answer: a
Explanation: The value of such constants can be calculated using algorithms which have time complexity in terms if O(nk) i.e polynomial time.
3. Which of the following cannot be solved using polynomial time?
a) Linear Programming
b) Greatest common divisor
c) Maximum matching
d) None of the mentioned
View Answer
Answer: d
Explanation: In graph theory, a matching or independent edge set in a graph G is a set of edges without common vertices. Given a graph (V, E), a matching M in G is a set of pairwise non adjacent edges i.e. no two edges share a common vertex.
4. The complexity class P consist of all the decision problems that can be solved by ___________using polynomial amount of computation time.
a) Push Down automata
b) DFA
c) NDFA
d) Deterministic Turing machine
View Answer
Answer: d
Explanation: All the decision problems that can be solved using a Deterministic turing machine using polynomial time to compute, all belong to the complexity class P.
5. A generalization of P class can be:
a) PTIME
b) DTIME
c) NP
d) None of the mentioned
View Answer
Answer: c
Explanation: P is a specific case of NP class, which is the class of decidable problems decidable by a non deterministic turing machine that runs in polynomial time.
6. Which of the following options are correct with reference to P-complete problems?
a) used for the problems which are difficult to solve in limited space
b) every problem in P can be reduced to it using proper reductions
c) complete problem for complexity class P
d) all of the mentioned
View Answer
Answer: d
Explanation:
The notion of P-complete decision problems is useful in the analysis of:
a) which problems are tough to parallelize effectively
b) which problems are difficult to solve in limited space
7. A problem X belongs to P complexity class if there exist ________ algorithm to solve that problem, such that the number of steps of the algorithms bounded by a polynomial in n, where n is the length of the input.
a) 1
b) 2
c) 3
d) all of the mentioned
View Answer
Answer: d
Explanation: A problem X belongs to P complexity class if there exist atleast 1 algorithm to solve that problem, such that the number of steps of the algorithms bounded by a polynomial in n, where n is the length of the input. Thus, all the options are correct.
8. Which of the following is a P-complete type of problem?
a) Circuit Value problem
b) Linear programming
c) Context free grammar membership
d) All of the mentioned
View Answer
Answer: d
Explanation: Given a context free grammar and a string, can the string be generated by the grammar? Such problems fall in the category of P-complete.
9. State true or false?
Statement: Given a turing machine, an input for the machine, and a number T(unary), does that machine halt on that input within the first T-steps?
The given problem is P-complete.
a) true
b) false
View Answer
Answer: a
Explanation: If we can parallelize a general simulation of a sequential computer, then we will be able to parallelize any program that runs on that computer. If this problem is in NC, then so every other problem in P.
10. In the above problem, if the input is binary, the class the problem belongs?
a) EXPSPACE
b) DLOGTIME
c) EXPTIME-complete
d) All of the mentioned
View Answer
Answer: c
Explanation: It is the set of all decision problems that have exponential run time i.e. solvable by deterministic turing machine in O(2p(n)) time, where p(n) is a polynomial function of n.
Sanfoundry Global Education & Learning Series – Automata Theory.
To practice all areas of Automata Theory for Interviews, here is complete set of 1000+ Multiple Choice Questions and Answers.
Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!
This set of Automata Theory Questions and Answers for Aptitude test focuses on “Node-Cover Problem, Hamilton Circuit Problem”.
1. Which of the given problems are NP-complete?
a) Node cover problems
b) Directed Hamilton Circuit Problem
c) Both (a) and (b)
d) None of the mentioned
View Answer
Answer: c
Explanation: Vertex cover or Node cover problem, and Hamilton Circuit problem, both are NP complete type of problems.
2. Which of the following problems do not belong to Karp’s 21 NP-complete problems?
a) Vertex Cover problems
b) Knapsack
c) 0-1 integer programming
d) None of the mentioned
View Answer
Answer: d
Explanation: There exists a set of 21 problems that are NP-complete and the set is called Karp’s 21 NP-complete problems.
3. Which of the following problems were reduced to Knapsack?
a) Exact Cover
b) Max Cut
c) 0-1 integer programming
d) None of the mentioned
View Answer
Answer: a
Explanation: Exact cover is a decision problem in computer science to determine if an exact cover exists.
4. An exact cover problem can be represented using:
a) incidence matrix
b) bipartite graph
c) both (a) and (b)
d) none of the mentioned
View Answer
Answer: c
Explanation: The relation ‘contains’ can be represented using a bipartite graph. The vertices of the graph can be divided into two disjoint sets, one representing the subset S and the other representing the elements of P and one edge for each subset in S;each node is included in exactly one of the edges forming the cover.
5. For which of the following, greedy algorithm finds a minimal vertex cover in polynomial time?
a) tree graphs
b) bipartite graphs
c) both (a) and (b)
d) none of the mentioned
View Answer
Answer: a
Explanation: For bipartite graphs, Konigs theorem allows the bipartite vertex problem to be solved in polynomial time.
6. Hamilton circuit problem can have the following version/s as per the input graph:
a) directed
b) undirected
c) both (a) and (b)
d) none of the mentioned
View Answer
Answer: c
Explanation: Hamilton circuit problem is a problem determining whether a Hamiltonian path(a path in an undirected or directed graph that visits each vertex exactly once) exists in a graph(directed or undirected).
7. Hamilton Circuit problem is a special case of ____________
a) travelling salesman problem
b) halting problem
c) hitting set
d) none of the mentioned
View Answer
Answer: a
Explanation: Hamilton circuit problem is a special case of travelling salesman problem, obtained by setting the distance between two cities to one if they are adjacent and two otherwise, and verifying that the total distance travelled is equal to n (if so, the route is a Hamiltonian circuit; if there is no Hamiltonian circuit then the shortest route will be longer).
8. Which of the following cannot solve Hamilton Circuit problem?
a) DNA Computer
b) Monte Carlo algorithm
c) Dynamic programming
d) None of the mentioned
View Answer
Answer: d
Explanation: Using Inclusion-exclusion principle, Andreas showed how to solve Hamilton Circuit problem in arbitrary n-vertex graphs by a Monte Carlo algorithm in time O(1.657n).
9. State true or false:
Statement: Hamiltonian cycles through any fixed edge is always even, so if one such cycle is given, the second one must also exists.
a) true
b) false
View Answer
Answer: a
Explanation: Handshaking lemma states that ‘Every finite undirected graph has an even number of vertices with odd degree.
10. Fibonacci number falls in the category of _________ combinatorics.
a) Algebric
b) Enumerative
c) Analytic
d) Extremal
View Answer
Answer: b
Explanation: Enumerative combinatorics is the most classical area of combinatorics and concentrates on counting the number of certain combinatorial objects. Fibonacci series is a basic example of Enumerative Combinatorics.
Sanfoundry Global Education & Learning Series – Automata Theory.
To practice all areas of Automata Theory for Aptitude test, here is complete set of 1000+ Multiple Choice Questions and Answers.
Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!
This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses on “PSPACE”.
1. All set of polynomial questions which can be solved by a turing machine using a polynomial amount of space:
a) PSPACE
b) NPSPACE
c) EXPSPACE
d) None of the mentioned
View Answer
Answer: a
Explanation: PSPACE is the problem class which contains all set of decision problems which can be solved using a turing machine taking polynomial amount of space.
2. PSPACE is strictly the super set of:
a) Regular language
b) Context free language
c) Context Sensitive Language
d) None of the mentioned
View Answer
Answer: c
Explanation: Membership of a string in a language defined by an arbitrary context sensitive grammar, or by an arbitrary determinisic context sensitive grammar, is a PSPACE -complete problem.
3. Savitch theorem relates to which of the following:
a) PSPACE=NPSPACE
b) Alternating Turing Machine
c) Time complexity
d) None of the mentioned
View Answer
Answer: a
Explanation: Some important conclusions of Savitch theorem includes:
a) PSPACE=NPSPACE: square of a polynomial function is still a polynomial function.
b) NL∈L2
4. The class PSPACE is closed under the following operations:
a) Union
b) Concatenation
c) Kleene
d) All of the mentioned
View Answer
Answer: d
Explanation: The closure property of PSPACE class includes :- Union, Concatenation and Kleene operation.
5. Correct the given order:
NL∈ P∈ NP∈ PH∈ PSPACE
a) NP∈ P∈ NL∈ PH∈ PSPACE
b) NL∈ PH∈ NP∈ P∈ PSPACE
c) NL∈ P∈ NP∈ PH∈ PSPACE
d) None of the mentioned
View Answer
Answer: c
Explanation: The given order is the only correct order and further PSPACE belongs to EXPTIME class and subsequently occurs EXPSPACE class.
6. NL ∈ PSPACE ∈ EXPSPACE
The given relation involves which of the following theorems?
a) Space hierarchy theorem
b) Savitch’s theorem
c) Both (a) and (b)
d) None of the mentioned
View Answer
Answer: c
Explanation: From space hierarchy theorem: NL ∈ NPSPACE, from Savitch’s theorem: NPSPACE= PSPACE.
7. Statement : All PSPACE problems can be reduced to PSPACE-complete problems.
State true or false:
a) true
b) false
View Answer
Answer: a
Explanation: PSPACE-complete problems are the most difficut problems is PSPACE. Finding a simple solution to PSPACE-complete means simple solution to all other problems in PSPACE because all PSPACE problems can be reduced to PSPACE-complete problems.
8. Without needing extra __________ we can simulate non deterministic turing machine using deterministic turing machine.
a) time
b) space
c) both time and space
d) none of the mentioned
View Answer
Answer: b
Explanation: Though it may use extra time, but as PSPACE=NPSPACE from savitch’s theorem, we can say that space taken is same for both the machins, deterministic as well as non-deterministic.
9. Complement of all the problems in PSPACE is ________
a) PSPACE
b) NL
c) P
d) All of the mentioned
View Answer
Answer: a
Explanation: The complement of all the problems in PSPACE are also in PSPACE, meaning co-PSPACE= PSPACE.
10. Which of the following PSPACE can be characterized into?
a) APTIME
b) AP
c) Quantom complexity class
d) None of the mentioned
View Answer
Answer: d
Explanation: An alternative characterization of PSPACE is a set of problems decidable by a turing machine in polynomial time, sometimes called, APTIME or AP.
Sanfoundry Global Education & Learning Series – Automata Theory.
To practice all areas of Automata Theory, here is complete set of 1000+ Multiple Choice Questions and Answers.
Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!
This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses on “Complexity Classes,Class RP and ZPP”.
1. Which among the following is smallest for n=50
a) 2n2
b) n2+3n+7
c) n3
d) 2n
View Answer
Answer: b
Explanation:
2n2=5000
n2+3n+7=2567
n3=125000
2n=1.13*1015
2. The space complexity of a turing machine is undefined if:
a) It is a multitape turing machine
b) If no string of length n causes T to use infinite number of tape squares
c) If some input of length n causes T to loop forever
d) None of the mentioned
View Answer
Answer: c
Explanation: If there exists an input string of length n that causes T to use an infinite number of tape squares, the space complexity of the turing machine is undefined.
3. In order to reduce the run time of a turing machine:
a) we can reduce the number of tapes
b) we can increase the number of tapes
c) use infinite tapes
d) none of the mentioned
View Answer
Answer: One way to reduce the run time can be to increase the number of tapes. Sometimes, using two tapes can be used to avoid back and forth motions altogether.
4. Which of the following are basic complexity classes for a function f:N->N?
a) Ntime(f)
b) Nspace(f)
c) Space(f)
d) All of the mentioned
View Answer
Answer: d
Explanation: Ntime(f): is a set of languages that can be accepted by a NTM T with non deterministic time complexity function t <=f. In all four cases, the machines are allowed to be multitape TM’s.
5. A function f is called __________ if there exists a TM T so that for any n and any input string of length n, T halts in exactly f(n) moves.
a) Step function
b) Step counting function
c) Inplace functions
d) None of the mentioned
View Answer
Answer: b
Explanation: If f is a step counting function, T is a TM halting in f(n) moves where n is the length of input string.
6. Let f: N->N be a step counting function. Then for some constant C, Time(f) is a proper subset of Time(_______)
a) O(nf)
b) O(n+f)
c) O(n2f2)
d) None of the mentioned
View Answer
Answer: c
Explanation: Using the encoding function, it is possible to show that if the function f is a step counting function, then the function Cn2(f(n))2 is the total number of moves required.
7. Which among the following is false?
If f=O(h) and g=O(k) for f,g,h,k:N->N, then
a) f+g = O(h+k)
b) fg = O(hk)
c) fg=O(hk)
d) None of the mentioned
View Answer
Answer: c
Explanation: f,g,h,k are partial functions and each is defined at all but a finite number of points.
8. Which of the following is not correct for ZPP?
a) zero error probabalistic polynomial time
b) it runs in non-polynomial time
c) it returns an answer yes, no or do not know
d) none of the mentioned
View Answer
Answer: b
Explanation: ZPP is zero error probabalistic polynomial time complexity class which run in polynomial time, returns an answer: yes, no or do not know.
9. ZPP is based on ________
a) Probabalistic turing machine
b) Alternative turing machine
c) Quantum turing machine
d) None of the mentioned
View Answer
Answer: a
Explanation: A probabalistic turing machine is a non deterministic turing machine which randomly chooses between the available transitions at each point according to some probability distribution.
10. ZPP is exactly equal to the ____________of the classes RP and co-RP.
a) Union
b) Intersection
c) Concatenation
d) Difference
View Answer
Answer: b
Explanation: To prove the following statement, we need to take in note that every problem in RP and co-RP has a Las-Vegas algorithm.
11. Suppose we have a las vegas algorithm C to prove ZPP is contained in RP and co-RP. Run C for double its expected running time.
By Markov’s inequality, the chance that it will answer before we stop is:
a) 1/2
b) 1/4
c) 1/3
d) none of the mentioned
View Answer
Answer: a
Explanation: This means the chance we’ll give the wrong answer on a YES instance, by stopping and yielding NO, is only 1/2, fitting the definition of an RP algorithm.
12. State true or false:
Statement: ZPP is closed under complement function.
a) true
b) false
View Answer
Answer: a
Explanation: ZPP is said to be closed under complement function i.e. ZPP=co-ZPP.
Sanfoundry Global Education & Learning Series – Automata Theory.
To practice all areas of Automata Theory, here is complete set of 1000+ Multiple Choice Questions and Answers.
Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!


Purpose of TGRestful is to provide pure REST examples for any thin or thick client API integration. (Android app, iOS app, JS framework like AngularJS etc.)
Project is being hosted @ http://amd.techgrains.com:8083/TGRESTful/ {...} for quick test without seeing the implementation.
| Method | URI | Description | Success | Failure |
|---|---|---|---|---|
GET |
/employee/1 | Employee having id {1} | 200 OK | 404 Not Found |
GET |
/employee/1/department/list | Employee having id {1} | 200 OK | 404 Not Found |
GET |
/employee/list | List of employees | 200 OK | |
GET |
/employee/list?name=Vishal | Filtered list of employees based on name contains {Vishal} | 200 OK | |
POST |
/employee/create | Creates Employee based on request params | 200 OK or 201 Created | 409 Conflict |
POST |
/employee/1/department/add | Adds Departments based on request params | 200 OK or 201 Created | 403 Forbidden, 404 Not Found |
PUT |
/employee/5 | Updates all the entity attributes based on request params. | 200 OK | 403 Forbidden, 404 Not Found, 409 Conflict |
PATCH |
/employee/5 | Updates Employee for only provided request params. | 200 OK | 403 Forbidden, 404 Not Found, 409 Conflict |
DELETE |
/employee/5 | Deletes Employee based on request params | 200 OK or 204 No Content | 404 Not Found |
DELETE |
/employee/5/department/12 | Deletes Department based on request params | 200 OK or 204 No Content | 404 Not Found |
Head
andOptions
are available for any request.
5XX
Status code may occur to any service based on connectivity and availablity of the instances which is indepedent to above examples.
GET
/employee/{id}HTTP 200 : /employee/1
{
"id": 1,
"name": "Vishal",
"designation": "Director",
"departments": [
{
"code": 10,
"name": "IT"
}
]
}
HTTP 404 /employee/100
{
"timestamp":<PHONE_NUMBER>124,
"status": "NOT_FOUND",
"error": "Not Found",
"message": "Employee not found for id - 100"
}
GET
/employee/{id}/department/listHTTP 200 : /employee/1/department/list
[
{
"code": 12,
"name": "Services"
},
{
"code": 13,
"name": "Products"
},
{
"code": 16,
"name": "Finance"
}
]
HTTP 404 : /employee/100/department/list
{
"timestamp":<PHONE_NUMBER>115,
"status": "NOT_FOUND",
"error": "Not Found",
"message": "Employee not found for id - 100"
}
GET
/employee/listRequest params: name={name}, designation={designation}
HTTP 200 : /employee/list?name=Snehal
[
{
"id": 6,
"name": "Snehal",
"designation": "Manager",
"departments": [
{
"code": 13,
"name": "Products"
}
]
}
]
POST
/employee/createRequest params: name={name}, designation={designation}
HTTP 200 : /employee/create (name=Karan, designation=Manager)
{
"id": 999,
"name": "Karan",
"designation": "Manager",
"departments": []
}
HTTP 409 : /employee/create (name=Satish, designation=Manager)
{
"timestamp":<PHONE_NUMBER>034,
"status": "CONFLICT",
"error": "Conflict",
"message" :"Employee already exists for name - Satish"
}
POST
/employee/{id}/department/addRequest params: department={departmentCode}
HTTP 200 : /employee/1/department/add (department=12)
{
"id": 1,
"name": "Vishal",
"designation": "Director",
"departments": [
{
"code": 10,
"name": "IT"
},
{
"code": 12,
"name": "Services"
}
]
}
HTTP 404 : /employee/100/department/add (department=13)
{
"timestamp":<PHONE_NUMBER>115,
"status": "NOT_FOUND",
"error": "Not Found",
"message": "Employee not found for id - 100"
}
HTTP 403 : /employee/1/department/add (department=10)
{
"timestamp":<PHONE_NUMBER>871,
"status": "FORBIDDEN",
"error": "Forbidden",
"message" :"Employee already has department code - 10"
}
PUT
/employee/{id}Request params: name={name}, designation={designation} (Required all the parameters of the entity for PUT)
HTTP 200 : /employee/5 (name=John, designation=Manager)
{
"id": 5,
"name": "John",
"designation": "Manager",
"departments": [
{
"code": 12,
"name": "Services"
},
{
"code": 13,
"name": "Products"
}
]
}
HTTP 403 : /employee/1 (name=John, designation=Manager)
{
"timestamp":<PHONE_NUMBER>258,
"status": "FORBIDDEN",
"error": "Forbidden",
"message": "System can't change designation of the Director."
}
HTTP 409 : /employee/5 (name=Karan, designation=Manager)
{
"timestamp":<PHONE_NUMBER>187,
"status": "CONFLICT",
"error": "Conflict",
"message" :"Employee already exists for name - Karan"
}
PATCH
/employee/{id}Request params: name={name} (Any subset of parameters of the entity for PATCH)
HTTP 200 : /employee/5 (name=John)
{
"id": 5,
"name": "John",
"designation": "Architect",
"departments": [
{
"code": 12,
"name": "Services"
},
{
"code": 13,
"name": "Products"
}
]
}
HTTP 403 : /employee/1 (name=John)
{
"timestamp":<PHONE_NUMBER>258,
"status": "FORBIDDEN",
"error": "Forbidden",
"message": "System can't change designation of the Director."
}
HTTP 409 : /employee/5 (name=Vilesh)
{
"timestamp":<PHONE_NUMBER>187,
"status": "CONFLICT",
"error": "Conflict",
"message" :"Employee already exists for name - Vilesh"
}
DELETE
/employee/{id}HTTP 200 : /employee/1
{Empty Response Body}
HTTP 404 /employee/100
{
"timestamp":<PHONE_NUMBER>124,
"status": "NOT_FOUND",
"error": "Not Found",
"message": "Employee not found for id - 100"
}
DELETE
/employee/{id}/department/{departmentCode}HTTP 200 : /employee/1/department/10
{
"id": 1,
"name": "Vishal",
"designation": "Director",
"departments": [],
"created":<PHONE_NUMBER>550,
"modified":<PHONE_NUMBER>550
}
HTTP 404 /employee/1/department/12
{
"timestamp":<PHONE_NUMBER>501,
"status": "NOT_FOUND",
"error": "Not Found",
"message": "Employee doesn't have department having code - 12"
}
If you want to run project, its simple Java Spring Boot MVC project with Gradle. (Java 1.8 & Gradle required to run)
$ gradle bootRun
By default it runs usuing port 8080
on local.
Code base already has example server side implementation of this RESTful services.
Any suggestions or recommendations are most welcome.
Please email me on<EMAIL_ADDRESS>with subject "TGRESTful" for easier reference and to have in proper mailbox folder. Thanks in advance!
Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at
http://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.


Desu Tara Sasaank
Home
About
Expertise
Contact Me
Skills
Hello There, I'm Desu Tara Sasaank
Full Stack Web Developer
Contact Me


--- layout: post title: Monkeys will pay for Paris Hilton smut date: 2006-09-20 00:00:00 categories: amusing animalia ---
Monkeys will pay for Paris Hilton smut: "A team from Duke University Medical Centre, led by neurobiologist Dr Michael Platt, offered 12 thirsty adult male rhesus macaque monkeys a choice between their favourite drink (Juicy Juice cherry juice, ABC News notes), and the chance to view pictures of their pack's dominant, "celebrity" monkey."


A computer monitor is an output device that displays information in graphical or pictorial form. A monitor usually comprises the display device, circuitry, casing and power supply.


| {{ account.addressBookName }} {{ account.id | squeeze }} | {{ account.balance | rai:'mnano' }} |
To bypass this warning, add your representative as trusted to your known representative list.
By clicking "change" you change to the suggested representative: {{ suggestedRep.alias }}
Click "manual" to choose your new representative yourself.


Body Stats Calculator
Your Measurements
Male
Female
Date
Age
Weight
Feet
Inches
Enter In Inches
Hips
Waist
Neck
Activity Level:
None
Light
Normal
Very
Extra
Submit
Reset
Sample
Your Stats
Body Fat Percentage
Body Mass Index
Body Mass Distribution
Total Daily Energy Expenditure
Progress Chart
Timeline
Date
Weight
BF %
Neck
Waist
Hip
Delete


Mike Allan is an ambitious and driven student enrolled at Western University, originally from the fantastic province of Newfoundland. He is pursuing a degree in Mechatronic Systems Engineering while concurrently completing an Honors in Business Administration from the Ivey Business School as a Loran Scholar.
He describes himself by the George Roter coined phrase — a "pragmatic idealist" because he does not think the polarity of realism vs. idealism should be a dichotomy. His work with Engineers Without Borders Canada has played a significant role in his personal development, both at his university's chapter and throughout his time working at the National Office in the summer of 2014. He is Western University's Chapter President for the 2016-17 school year.
He has a wide range of passions, including athletics, music, languages, entrepreneurship, technology, and social change. Mike is striving to find a way to amalgamate his passions for business, technology, and social justice. To contact him, please head over to the contact page.
Right now, Mike is at Western in his fourth year of study. When not in class or doing schoolwork, Mike spends a lot of his time with Engineers Without Borders as this year's chapter president at Western. Outside of that, Mike is an active member in the UWO Salsa club, plays intramural volleyball and Ultimate Frisbee, and is the VP Finance of the Western Rubik's Cube Club.


Load packages
library(tidyverse)
library(lsr)
Motivation
Recently, I listened to the great Paul Meehl in the audioscripts of some lectures of him. There, he asked the students
what’s the mean value of the upper half of a Gaussian distribution?
Let’s explore that using simulation techniques.
Simulation time
Let’s draw some instances from a standard Normal distribution, \(X\).
n <- 1e05
x <- rnorm(n)
Mean and SD in our sample are quite close to what can be expected:
mean(x)
#> [1] 0.002953451
sd(x)
#> [1] 0.9992983
aad(x)
#> [1] 0.7972097
Note that the aad is 0.8 in a standard normal distribution.
Upper half
Let’s put the data into a tibble.
df <- tibble(x = x,
upper_half = ifelse(x >= 0, TRUE, FALSE))
df %>%
group_by(upper_half) %>%
summarise(avg_half = mean(x),
sd_half = sd(x),
var_half = var(x),
md_half = median(x),
iqr_half = IQR(x),
aad_half = aad(x),
n_half = n())
#> # A tibble: 2 x 8
#> upper_half avg_half sd_half var_half md_half iqr_half aad_half n_half
#> <lgl> <dbl> <dbl> <dbl> <dbl> <dbl> <dbl> <int>
#> 1 FALSE -0.797 0.604 0.365 -0.672 0.826 0.483 49822
#> 2 TRUE 0.797 0.601 0.361 0.676 0.831 0.482 50178
As can be seen the average in the halves is about 0.8 standard units away from the cut point (zero).
Some theory: Half normal distribution
The half-normal distribution has this expected value: \(E[Y]=\mu ={\frac {\sigma {\sqrt {2}}}{\sqrt {\pi }}}\).
From the Wikipedia page:
In more simple terms, we have this expected value:
E = 1 * sqrt(2) / sqrt(pi)
E
#> [1] 0.7978846
In other words, about 0.8 standard units, just as we saw above.
Note that 1
refers to the variance of \(X\) which is 1.
Regarding the variance, according to the Wikipedia page sited above, \((Y)=\sigma ^{2}\left(1-{\frac {2}{\pi }}\right)\)
Var = 1 * (1 - (2/pi))
Var
#> [1] 0.3633802
Note that this parameter is proportional to the Variance of \(X\).
This value does match nicely the simulated value from above.
However, according to Math Wolfram, \(V = \frac{-2 + \pi}{2 \theta^2}\).
Wikipedia states that Wolfram Math uses this parametrization:
\[\theta = \sqrt{\pi/2}\].
That is,
theta = sqrt(pi/2)
theta
#> [1] 1.253314
Var2 = (-2+pi) / (2 * theta^2)
Var2
#> [1] 0.3633802
Parameter estimation
According to Wikipedia, the \(\sigma\) can be estimated as such:
sigma_hat = sqrt((1/n) * sum(x^2))
sigma_hat
#> [1] 0.9992977


title = "Notifications" url = "/notifications" layout = "default" hidden = "0" [NotificationList] onlyUnread = "1" autoMarkAsRead = "0" showLimit = "20" ==


Foot fetish: Nibbles a specialty at Indonesian restaurant
by AFPAs he scarfed down a traditional Indonesian meal, Adi Karyanov got himself the two-in-one special at a new restaurant offering pedicures by fish.
The tables and chairs at Soto Cokro Kembang in Indonesia’s cultural capital Yogyakarta sit in ankle-deep water, home to thousands of little fish that nibble dead skin off the feet of diners.
“I felt the fish biting my feet — it was ticklish but nice,” Karyanov said.
“They make it fun to eat here. It’s kind of unique.”
Many spas across southeast Asia have for years touted a fishy pedicure as an unproven but novel way of treating various skin conditions.
But restaurant owner Imam Nur, who opened in June, has gone a step further by offering it alongside his traditional Javanese “sole food”.
Nur credits his father for coming up with the idea for the open-air restaurant, which has some 7,000 Red Nile Tilapia swimming around its patrons.
“We initially opened this restaurant just for locals living nearby,” he said.
“But what’s happening now is beyond what we had initially planned. It’s become like culinary tourism. Many people are coming here from different cities.”
Pressing fish into service to remove dead skin is not without controversy.
Some cities in North America and Europe have banned it over concerns about bacterial outbreaks, while People for the Ethical Treatment of Animals (PETA) has warned over both the health risks and possible cruelty to animals.
Still, visitors like Anna Widia were keen to give the fish treatment a whirl.
“I’ve never seen any place like this,” she said.
“And it’s big enough to bring the whole family.”


Coffee machine monitoring
This is a sample application implemented for demonstration purposes using AWS IoT Greengrass and AWS Lambda
Machine 113>
{%if data_per_device and '1' in data_per_device %}
Cups served: {{data_per_device['1'].total_cups}}
Bean usage: {{data_per_device['1'].total_beans_usage}} g
{% endif %} {% if not data_per_device or '1' not in data_per_device %} No telemetry on caffee consumption is available yet {% endif %}
Bean usage: {{data_per_device['1'].total_beans_usage}} g
{% endif %} {% if not data_per_device or '1' not in data_per_device %} No telemetry on caffee consumption is available yet {% endif %}
Machine 2
{%if data_per_device and '2' in data_per_device %}
Cups served: {{data_per_device['2'].total_cups}}
Bean usage: {{data_per_device['2'].total_beans_usage}} g
{% endif %} {% if not data_per_device or '2' not in data_per_device %} No telemetry on caffee consumption is available yetx {% endif %}
Bean usage: {{data_per_device['2'].total_beans_usage}} g
{% endif %} {% if not data_per_device or '2' not in data_per_device %} No telemetry on caffee consumption is available yetx {% endif %}


The eplet ? antibody-reactive!
➔ Probability of not beeing antibody-reactive: ?
➔ Probability of beeing antibody-reactive: ?
Note: antibody-reactive HLA eplets are the ones against the recipient may present important anti-HLA antibodies.
If the donor shares one of these eplets, the risk of the recipient developing antibody-mediated rejection against the graft will be greater.
Remember that all results presented here are based on probabilities. This tool is for research use only!


AHIA - Avoid Hiding Inherited Attributes
Detects when attributes declared in child classes hide inherited attributes.
Wrong
int attr1;
// something...;
}
class Animal {
int attr1;
}
Tip: Rename child class attribute.
Right
int mnkyAttr1;
// something...;
}
class Animal {
int attr1;
}


See GeoDjango.org for help and installation instructions
Credits: http://code.google.com/p/geodjango-basic-apps/


{% extends "base.html" %} {% import "task/action/task_module.html" as task_module %} {% block content %}
Are you sure you want to delete the action?
{{p.action.Name}} {{p.action.description}}
Are you sure you want to RUN the task?
{{p.task.name}} {{p.task.description}}


Mentor Me
Log In
Home
Contact
About
Pricing
Log In
Home
Contact
About
Pricing
Contact us!
Fill out this form and someone will be with you shortly!
Name
Email
Phone
Business Type
Message
send form


Two new Canon EOS M mirrorless cameras could be announced in 2020
by Sharmishta SarkarTwo new Canon EOS M mirrorless cameras could be announced in 2020
An EOS M50 Mark II could be on the cards
(Image credit: Future)
Canon has been busy this year, what with the launch of the EOS 90D and EOS M6 Mark II. And going by the latest rumors, 2020 will be even busier for the Japanese camera maker.
We already know that the pro-sports EOS 1D X Mark III DSLR will be announced early next year, but Canon Rumors is reporting that two more crop sensor mirrorless cameras will be added to the company's growing line-up in 2020.
One of them is rumored to be a 24MP APS-C snapper that will come with eye-detect autofocus and Canon's tried-and-tested superb Dual Pixel CMOS autofocus technology (which increases AF speed and accuracy in live view mode) available on a 3-inch vari-angle rear touchscreen.
Canon Rumors goes even further to put a price tag of $849 for a kit with a lens for this rumored EOS M camera, which will reportedly be announced in "before July 2020".
- 10 best budget cameras available right now
- Best Canon cameras in 2019
- 10 best entry-level mirrorless cameras
A new mirrorless marvel?
The EOS M50 was the first Canon camera to debut the Digic 8 processor, giving this entry-level mirrorless snapper plenty of power. No wonder it soon became one of our favorite affordable mirrorless cameras.
Although it was launched only in 2018, Canon Rumors reports that the second EOS M camera to launch in 2020 will likely be a refresh of the M50. With the EOS M6 Mark II already boasting a 32.5MP APS-C CMOS sensor, we wouldn't be surprised to see the same make its way into the EOS M50 Mark II.
While Canon Rumors lists the Digic 8 imaging engine as accompanying the higher resolution sensor, we'd love to see the Digic 9 (which could be debuted in the EOS 1D X Mark III) make its way to the newer version of the M50, giving the rumored CSC (compact system camera) a massive boost in performance.
If the other rumored specs of the M50 Mark II have any element of truth to them, then we're likely going to see the upcoming camera capable of 4K video recording at both 24fps and 30fps, with Full HD (1080p) capture at up to 120fps. The rear touchscreen will reportedly be a 3-inch vari-angle panel with 1,040K-dot resolution.
If a refresh of the EOS M50 is truly in the cards, Canon Rumors says it will be announced some time in September 2020. So don't get too excited just yet, as these are still rumors and things can change between now and then.
- In the meantime, we've rounded up the best mirrorless cameras you can buy in 2019


This is news box
This is news content
Welcome to SEScurm the place where you can find everything interesting about IT department
This is news content
this is events content
This is links content
More lines
more lines
and more lines


[ Back to the map ]
Change log
-
2023-8-11
- Moved db credentials to env variable.
-
2023-3-13
- Added a filter to only label bright stars.
-
2021-1-3
- The map will now label only the brighter star if two are right next to each other,
to improve readability.
-
2020-12-31
- Imported the list of proper names from the IAU
-
2020-12-30
- Rewrote all the old code to make it more efficient. Large maps that used to
take several seconds to render are now done in milliseconds.
- Updated the interface, keeping all the existing features.
- Upgraded to the latest HYG database (v3).
- Readded about 120 of the Star Trek stars that were missing from the db.
- Moved to new domain.
- Added to github.