WorksheetsAutomata Theory Quiz
Total questions: 20
Worksheet time: 20mins
Which of the following statements is true about a string in the context of formal languages?
It is an infinite sequence of symbols.
It is a finite sequence of symbols from an alphabet.
It is a set of symbols.
It can contain symbols not in the alphabet.
A language is considered a regular language if it can be recognized by a:
Context-Free Grammar
Pushdown Automaton
Finite State Machine
Turing Machine
What is a language in the Theory of Computation?
A set of states in a Finite State Machine.
A set of strings over a given alphabet.
A regular expression.
The alphabet of symbols itself.
In a Deterministic Finite State Machine (FSM), for a given input symbol and a given state, how many possible next states are there?
Zero or one.
Exactly one.
One or more.
Any number.
What is the key difference between a Deterministic FSM (DFSM) and a Nondeterministic FSM (NFSM)?
An NFSM's transition function can result in a set of states.
NFSMs have more states than equivalent DFSMs.
DFSMs cannot have transitions on the empty string (ϵ).
NFSMs can have multiple start states.
What is the primary purpose of minimizing an FSM?
To add more accepting states.
To find the FSM with the fewest states that accepts the same language.
To make it easier to design.
To convert it to a regular expression.
The regular expression `a*` matches which of the following strings?
Any string consisting of zero or more 'a's.
Any string of one or more 'a's.
Only 'a'
A string with no 'a's at all.
If two states in a DFSM are indistinguishable, what does this imply for FSM minimization?
They can be merged into a single state.
The FSM cannot be minimized.
One of them must be an accepting state and the other not.
They have different transitions on the same input symbol.
The regular expression `(a|b)c` describes which language?
The set of strings containing 'a' or 'b' or 'c'.
The set of strings { 'ac', 'bc' }.
The set of strings { 'abc' }.
The string 'abc' or the string 'c'.
What does the transition δ(q0,a)=q1 represent in an FSM?
The only valid input symbol is 'a'.
When in state q0 and reading the input symbol 'a', the machine moves to state q1.
The language accepted by the FSM is 'a'.
The FSM starts in state q1.
