Unit 9 - Regular Languages Flashcards
What is a mealy machine?
A mealy machine is special type of Finite State Machine that generates an output on each state transition.
What does a * mean in regular expressions?
A * indicates there are 0 or more of the preceding element.
What does a + indicate in regular expressions?
A + indicates that there are at least one of the preceding element.
What does a ? indicate in regular expressions?
A ? indicates that there are zero or one of the preceding element.
What are the two required states for a Turing machine?
A Turing machine must have a start state and at least one halt state.
What is the format for a transition function in a state diagram?
δ (Current state, Input symbol) = (Next state, Output symbol, Head move)
What is the Universal Turing Machine?
The Universal Turing Machine was the first Turing machine that could take input data but could also take a Turing machine definition as input, allowing it to represent all Turing machines.
