Push-down Automata (PDA)

1. The production of the form A->B , where A and B are non terminals is called
a) Null production
b) Unit production
c) Greibach Normal Form
d) Chomsky Normal Form
Answer: b
Explanation: A->ε is termed as Null production while A->B is termed as Unit production.

2. Halting states are of two types. They are:
a) Accept and Reject
b) Reject and Allow
c) Start and Reject
d) None of the mentioned
Answer: a
Explanation: Halting states are the new tuple members introduced in turing machine and is of two types: Accept Halting State and Reject Halting State.

3. A push down automata can be represented as:
PDA= ε-NFA +[stack] State true or false:
a) true
b) false
Answer: a
Explanation:

4. A pushdown automata can be defined as: (Q, ∑, G, q0, z0, A, d)
What does the symbol z0 represents?
a) an element of G
b) initial stack symbol
c) top stack alphabet
d) all of the mentioned
Answer: d
Explanation: z0 is the initial stack symbol, is an element of G. Other symbols like d represents the transition function of the machine.

5. Which of the following correctly recognize the symbol ‘|-‘ in context to PDA?
a) Moves
b) transition function
c) or/not symbol
d) none of the mentioned
Answer: a
Explanation: Using this notation, we can define moves and further acceptance of a string by the machine.

6. Which among the following is true for the given statement?
Statement :If there are strings R and T in a language L so that R is prefix of T and R is not equivalent to T.
a) No DPDA can accept L by empty stack
b) DPDA can accept L by an empty stack
c) L is regular
d) None of the mentioned
Answer: a
Explanation: If M is a DPDA accepting L by an empty stsck, R and T are distinct strings in L, and R is a prefix of T, then the sequence of moves M must make in order to accept R leaves the stack empty, since R∈L. But then T cannot be accepted, since M cant move with an empty stack.

7. Which of the following can be accepted by a DPDA?
a) The set of even length palindrome over {a,b}
b) The set of odd length palindrome over {a,b}
c) {xxc| where c stands for the complement,{0,1}}
d) None of the mentioned
Answer: d
Explanation: Theorem: The language pal of palindromes over the alphabet {0,1} cannot be accepted by any finite automaton , and it is therefore not regular.

8. For a counter automaton, with the symbols A and Z0, the string on the stack is always in the form of __________
a) A
b) AnZ0, n>=0
c) Z0An, n>=0
d) None of the mentioned
Answer: b
Explanation:The possible change in the stack contents is a change in the number of A’s on the stack.

9. State true or false:
Statement: Counter Automaton can exist for the language L={0i1i|i>=0}
a) true
b) false
Answer: a
Explanation: The PDA works as follows. Instead of saving excess 0’s or 1’s on the stack, we save *’s and use two different states to indicate which symbol there is currently a surplus of. The state q0 is the initial state and the only accepting state.

10. Let ∑={0,1}* and the grammar G be:
S->ε
S->SS
S->0S1|1S0
State which of the following is true for the given
a) Language of all and only Balanced strings
b) It contains equal number of 0’s and 1’s
c) Ambiguous Grammar
d) All of the mentioned
Answer: d
Explanation: A string is said to be balanced if it consist of equal number of 0’s and 1’s.

11. A push down automaton employs ________ data structure.
a) Queue
b) Linked List
c) Hash Table
d) Stack
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.

12. State true or false:
Statement: The operations of PDA never work on elements, other than the top.
a) true
b) false
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.

13. 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
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.

14. 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
Answer: d
Explanation: The 10-tuple can be stated as: NSA= ‹Q,Σ,Γ,δ,q0,Z0,F,[,],]›.

15. Push down automata accepts _________ languages.
a) Type 3
b) Type 2
c) Type 1
d) Type 0
Answer: b
Explanation: Push down automata is for Context free languages and they are termed as Type 2 languages according to Chomsky hierarchy.

16. 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
Answer: d
Explanation: NSPACE or non deterministic space is the computational resource describing the memory space for a non deterministic turing machine.

17. 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
Answer: d
Explanation: This class of automata can recognize a set of context free languages like {anbn|n belongs to N}

18. Which of the operations are eligible in PDA?
a) Push
b) Delete
c) Insert
d) Pop
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.

19. 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
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.

20. 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
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.

21. If two sets, R and T has no elements in common i.e. RÇT=Æ, then the sets are called
a) Complement
b) Union
c) Disjoint
d) Connected
Answer: c
Explanation: Two sets are called disjoint if they have no elements in common i.e. RÇT=Æ.

22. Which among the following is not a part of the Context free grammar tuple?
a) End symbol
b) Start symbol
c) Variable
d) Production
Answer: a
Explanation: The tuple definition of context free grammar is: (V, T, P, S) where V=set of variables, T=set of terminals, P=production, S= Starting Variable.

23. A context free grammar is a ___________
a) English grammar
b) Regular grammar
c) Context sensitive grammar
d) None of the mentioned
Answer: c
Explanation: Context free grammar is the set which belongs to the set of context free grammar. Similarly, Regular grammar is a set which belongs to the the set of Context free grammar.

24. The closure property of context free grammar includes :
a) Kleene
b) Concatenation
c) Union
d) All of the mentioned
Answer: d
Explanation: Context free grammars are closed under kleene operation, union and concatenation too.

25. Which of the following automata takes stack as auxiliary storage?
a) Finite automata
b) Push down automata
c) Turing machine
d) All of the mentioned
Answer: b
Explanation: Pushdown Automaton uses stack as an auxiliary storage for its operations. Turing machines use Queue for the same.

26. Which of the following automata takes queue as an auxiliary storage?
a) Finite automata
b) Push down automata
c) Turing machine
d) All of the mentioned
Answer: c
Explanation: Pushdown Automaton uses stack as an auxiliary storage for its operations. Turing machines use Queue for the same.

27. A context free grammar can be recognized by
a) Push down automata
b) 2 way linearly bounded automata
c) Both (a) and (b)
d) None of the mentioned
Answer: c
Explanation: A linearly bounded automata is a restricted non deterministic turing machine which is capable of accepting ant context free grammar.

28. A null production can be referred to as:
a) String
b) Symbol
c) Word
d) All of the mentioned
Answer: a
Explanation: Null production is always taken as a string in computational theory.

29. The context free grammar which generates a Regular Language is termed as:
a) Context Regular Grammar
b) Regular Grammar
c) Context Sensitive Grammar
d) None of the mentioned
Answer: b
Explanation: Regular grammar is a subset of Context free grammar. The CFGs which produces a language for which a finite automaton can be created is called Regular grammar.

30. NPDA stands for
a) Non-Deterministic Push Down Automata
b) Null-Push Down Automata
c) Nested Push Down Automata
d) All of the mentioned
Answer: a
Explanation: NPDA stands for non-deterministic push down automata whereas DPDA stands for deterministic push down automata.

31. The transition a Push down automaton makes is additionally dependent upon the:
a) stack
b) input tape
c) terminals
d) none of the mentioned
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.

32. 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
Answer: a
Explanation: A machine configuration is an element of K×Σ*×Γ*.
(p,w,γ) = (current state, unprocessed input, stack content).

33. |-* is the __________ closure of |-
a) symmetric and reflexive
b) transitive and reflexive
c) symmetric and transitive
d) none of the mentioned
Answer: b
Explanation: A string w is accepted by a PDA if and only if (s,w, e) |-* (f, e, e)

34. 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
Answer: d
Explanation: The empty stack in the end is our requirement relative to finite state automatons.

35. 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
Answer: a
Explanation: A Deterministic Push Down Automata is a Push Down Automata in which no state p has two or more transitions.

36. 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
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

37. 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
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.

38. 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
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.

39. Which of the following is a simulator for non deterministic automata?
a) JFLAP
b) Gedit
c) FAUTO
d) None of the mentioned
Answer: a
Explanation: JFLAP is a software for experimenting with formal topics including NFA, NPDA, multi-tape turing machines and L-systems.

40. Finite-state acceptors for the nested words can be:
a) nested word automata
b) push down automata
c) ndfa
d) none of the mentioned
Answer: a
Explanation: The linear encodings of languages accepted by finite nested word automata gives the class of ‘visibly pushdown automata’.

41. Which of the following is analogous to the following?
:NFA and NPDA
a) Regular language and Context Free language
b) Regular language and Context Sensitive language
c) Context free language and Context Sensitive language
d) None of the mentioned
Answer: a
Explanation: All regular languages can be accepted by a non deterministic finite automata and all context free languages can be accepted by a non deterministic push down automata.

42. Let T={p, q, r, s, t}. The number of strings in S* of length 4 such that no symbols can be repeated.
a) 120
b) 625
c) 360
d) 36
Answer: b
Explanation: Using the permutation rule, we can calculate that there will be total of 625 permutations on 5 elements taking 4 as the length.

43. Which of the following relates to Chomsky hierarchy?
a) Regular<CFL<CSL<Unrestricted
b) CFL<CSL<Unrestricted<Regular
c) CSL<Unrestricted<CF<Regular
d) None of the mentioned
Answer: a
Explanation: The chomsky hierarchy lays down the following order: Regular<CFL<CSL<Unrestricted

44. A language is accepted by a push down automata if it is:
a) regular
b) context free
c) both (a) and (b)
d) none of the mentioned
Answer: c
Explanation: All the regular languages are the subset to context free languages and thus can be accepted using push down automata.

45. Which of the following is an incorrect regular expression identity?
a) R+f=R
b) eR=e
c) Rf=f
d) None of the mentioned
Answer: b
Explanation: e is the identity for concatenation. Thus, eR=R.

46. Which of the following strings do not belong the given regular expression?
(a)*(a+cba)
a) aa
b) aaa
c) acba
d) acbacba
Answer: d
Explanation: The string acbacba is unacceptable by the regular expression (a)*(a+cba).

47. Which of the following regular expression allows strings on {a,b}* with length n where n is a multiple of 4.
a) (a+b+ab+ba+aa+bb+aba+bab+abab+baba)*
b) (bbbb+aaaa)*
c) ((a+b)(a+b)(a+b)(a+b))*
d) None of the mentioned
Answer: c
Explanation: Other mentioned options do not many of the combinations while option c seems most reliable.

48. Which of the following strings is not generated by the given grammar:
S->SaSbS|e
a) aabb
b) abab
c) abaabb
d) None of the mentioned
Answer: d
Explanation: All the given options are generated by the given grammar. Using the methods of left and right derivations, it is simpler to look for string which a grammar can generate.

49. abb*c denotes which of the following?
a) {abnc|n=0}
b) {abnc|n=1}
c) {anbc|n=0}
d) {abcn|n>0}
Answer: b
Explanation: Here, the first mentioned b is fixed while the other can be zero or can be repeated any number of time.

50. The following denotion belongs to which type of language:
G=(V, T, P, S)
a) Regular grammar
b) Context free grammar
c) Context Sensitive grammar
d) All of the mentioned
Answer: b
Explanation: Ant formal grammar is represented using a 4-tuple definition where V= finite set of variables, T= set of terminal characters, P=set of productions and S= Starting Variable with certain conditions based on the type of formal grammar.