Quiz on Automata Theory

What is the main difference between DFA and NFA?

• DFA can have multiple transitions for the same input symbol.

• NFA cannot recognize any language.

• NFA can have multiple transitions for the same input symbol.

• DFA can have epsilon-transitions.

What is the purpose of eliminating epsilon-transitions from an NFA?

• To make the NFA more complex.

• To convert NFA to DFA.

• To simplify the NFA.

• To increase the number of states.

Which of the following is a type of FSM with output?

• Regular Expression

• Context-Free Grammar

• Moore machine

• Nondeterministic Finite Automata

What does the Chomsky hierarchy classify?

• Types of grammars

• Types of automata

• Types of algorithms

• Types of programming languages

What is a characteristic of a Moore machine?

• Output depends on the current state and input.

• It cannot be represented by a state diagram.

• Output depends only on the current state.

• It has no states.

Which of the following automata can be used to recognize regular languages?

• Deterministic Finite Automata

• Pushdown Automata

• Turing Machine

• Linear Bounded Automata

What is the primary function of a Turing machine?

• To parse context-free languages

• To simulate any algorithm

• To recognize regular expressions

• To convert grammars to automata

Which of the following statements is true about context-free grammars?

• They cannot be parsed by any algorithm.

• They can describe nested structures.

• They can generate all regular languages.

• They can be represented by finite automata.

What is the main advantage of using a DFA over an NFA?

• DFA can be more easily implemented in hardware.

• NFA is always faster than DFA.

• NFA requires fewer states than DFA.

• DFA can recognize more complex languages.

What is the significance of the pumping lemma in formal languages?

• It helps in proving that certain languages are regular.

• It describes the limitations of Turing machines.

• It defines the structure of context-free grammars.

• It is used to convert NFAs to DFAs.