1. Which of the following is an example of a Pushdown Automaton (PDA)?
a) Deterministic Finite Automaton (DFA)\
b) Non-deterministic Finite Automaton (NFA)\
c) Deterministic Pushdown Automaton (DPDA)\
d) Non-deterministic Pushdown Automaton (NPDA)
Answer: d) Non-deterministic Pushdown Automaton (NPDA)
Explanation: PDAs extend the capabilities of DFAs and NFAs by allowing them to use a stack, enabling more complex processing of languages, and NPDA allows for multiple possible transitions from a given state and input symbol.
2. Which type of PDA requires that for each state and input symbol, there is only one possible transition?
a) Non-deterministic PDA (NPDA)\
b) Deterministic PDA (DPDA)\
c) Deterministic Finite Automaton (DFA)\
d) Non-deterministic Finite Automaton (NFA)
Answer: b) Deterministic PDA (DPDA)
Explanation: In DPDA, the transition function provides only one possible next state for each state and input symbol pair.
3. What is the primary difference between a Deterministic Pushdown Automaton (DPDA) and a Non-deterministic Pushdown Automaton (NPDA)?
a) DPDA has a finite number of states, while NPDA has an infinite number of states.\
b) DPDA always halts on any input, while NPDA may not halt on some inputs.\
c) DPDA can have multiple possible transitions from a state for a given input, while NPDA has only one transition.\
d) DPDA uses a stack with a limited size, while NPDA uses an unbounded stack.
Answer: c) DPDA can have multiple possible transitions from a state for a given input, while NPDA has only one transition.
Explanation: NPDA allows for non-deterministic transitions, meaning there can be multiple possible next states for a given state and input symbol pair.
4. Which of the following describes the conversion of a Pushdown Automaton (PDA) into a Context-Free Grammar (CFG)?
a) CFG to PDA conversion\
b) PDA to CFG conversion\
c) PDA to DFA conversion\
d) NFA to CFG conversion
Answer: b) PDA to CFG conversion
Explanation: This process involves creating a context-free grammar that generates the same language as the given PDA.
5. What does a Petri net model represent?
a) A graphical modeling tool used for software development\
b) A mathematical modeling tool used for analyzing concurrent systems\
c) A type of network architecture used in computer networking\
d) A data structure used for organizing information in databases
Answer: b) A mathematical modeling tool used for analyzing concurrent systems
Explanation: Petri nets are mathematical models used to represent and analyze systems with concurrent processes.
6. Which of the following represents a formal language generated by a Pushdown Automaton (PDA)?
a) Regular language\
b) Context-free language\
c) Context-sensitive language\
d) Unrestricted grammar language
Answer: b) Context-free language
Explanation: PDAs are capable of recognizing and generating context-free languages.
7. Which of the following automata can recognize languages that a Deterministic Finite Automaton (DFA) cannot?
a) Non-deterministic Finite Automaton (NFA)\
b) Deterministic Pushdown Automaton (DPDA)\
c) Non-deterministic Pushdown Automaton (NPDA)\
d) Turing Machine
Answer: c) Non-deterministic Pushdown Automaton (NPDA)
Explanation: NPDA can recognize non-context-free languages, which are beyond the capabilities of DFAs.
8. What is a characteristic feature of a Petri net model?
a) Transition rules\
b) Stack operations\
c) Finite control\
d) Parallelism
Answer: d) Parallelism
Explanation: Petri nets represent systems with concurrent processes, allowing for modeling of parallelism.
9. Which of the following represents the conversion of a Context-Free Grammar (CFG) into a Pushdown Automaton (PDA)?
a) CFG to PDA conversion\
b) PDA to CFG conversion\
c) PDA to DFA conversion\
d) NFA to CFG conversion
Answer: a) CFG to PDA conversion
Explanation: This process involves creating a PDA that recognizes the language generated by the given CFG.
10. Which type of Pushdown Automaton (PDA) has a limited number of transitions from a state for a given input symbol?
a) Non-deterministic PDA (NPDA)\
b) Deterministic PDA (DPDA)\
c) Non-deterministic Finite Automaton (NFA)\
d) Deterministic Finite Automaton (DFA)
Answer: b) Deterministic PDA (DPDA)
Explanation: DPDA restricts the number of possible transitions from a state for a given input symbol, ensuring determinism.