Regular Languages Flashcards
(33 cards)
What is a Finite State Machine (FSM)?
A model that shows how a machine or system can change from one state to another based on an external input
What are the 2 ways a FSM can be represented?
- State Transition Diagram
- State Transition Table
What are the essential components of a FSM?
- A finite set of input symbols (its alphabet)
- A finite set of states that the machine can be in
- An initial state - S0
- A state-transition function which determines which state to transition to based on the current state and input
- One or more accepting states
In how many states can a FSM be in at once?
1
What is a dead state?
When it enters a state where it is no longer possible for it to reach an accepting state therefore the input must be invalid.
What are some systems that FSM might be used to model?
- Digital (hardware) systems
- Software compilers
- Syntax parsing
- Network protocols
- Games
What is the “language” of a FSM?
The set of all possible input strings that follow a path from the initial state to an accepting state.
What does it mean for a finite state machine to be deterministic?
The next state is only dependent on the current state and input and hence requires no memory.
What is a Finite State Automata?
A FSM that doesn’t produce an output that always has an initial state and at least one accepting state
What is a Mealy Machine?
A FSM that produces an output as its inputs are being processed rather than once an accepting state has been reached
What are some differences of the Mealy Machines when compared to automata?
- Produce an output while the inputs are being processed
- They do not have accepting states
What are the uses of Mealy Machines?
- Encrypting a message into cipher text
- Controlling traffic lights
- Vending machine payment collection and display of amount remaining
- Digital logic circuits
What is a set?
An unordered collection of values in which each value occurs at most once
What is the Cartesian Product of two sets?
The Cartesian product of two sets, A and B, is written as A x B and is the set of all ordered pairs (a,b) where a ∈ A and b ∈ B
What is a subset?
A subset of S is a set whose values are all members of S. Written as A ⊆ B
What is a proper subset?
A proper subset of S is a set where every value is a member of S but it does not contain all members of S. Written as A ⊂ B.
What is the cardinality of a finite set?
The number of items in the finite set
What are the different set operations?
- Union - ∪ - all elements in either set or both
- Intersection - ∩ - elements shared by both sets
- Difference - / - A/B is all the elements in A but not in B (also written as A-B)
What is the union of two sets?
The union of two sets , A and B, will contain all unique values in A and B.
What is the intersection of two sets?
The intersection of two sets, A and B, will contain all values that are present in both A and B.
What is the difference of two sets?
The difference of two sets, A and B, will contain all the elements that are in set A but are NOT in set B.
What is a finite set?
A set whose elements can be counted off by natural numbers (at which point the set stops).
The number of items in the set is referred to as its cardinality.
How to show a compact representation of a string with equal numbers of 1s and 0s?
{ 0n1n | n >= 1}
where n must be a countable number
What is an infinite set?
A set with an infinite number of items.
