Unit 9 Flashcards
Define Finite State Machine
An abstract model of a computation used to design a range of computer programs
What are the 5 states of FSMs?
States, transitions, transition conditions, start state and accept state
How can FSMs be used in language parsing?
You can enter a string into a FSM character by character, if the FSM is in the accept state at the end of the string that means that the string is valid for that language
What is the difference between a Mealy machine and a FSM?
A mealy machine generates an output for each transition. This means you can input a string and it will translate it for you.
What determines a mealy machine’s output?
The current state and the input from the user
What does it mean for a FSM to be deterministic?
Only a single transition can be assigned for each combination of state and input
How do you format the transition conditions on a mealy machine?
<input></input> / <output></output>
Define language parsing
The process of analysing that a string of symbols conforms to the syntax rules of a language
What are the two ways to display a mealy machine?
As a diagram or a state transition table
What are the 4 areas shown in a mealy machine state transition table?
Input, current state, output, next state
Define set
A well defined collection of objects
What is the name for an item in a set?
Element/member
What are two rules for members in sets?
- Each member can only occur once
- The members in a set must remain unordered
How do you refer to a set and its corresponding members?
The set it referred to using an uppercase letter and the corresponding members are referred to using a lowercase letter
How are sets an example of abstraction?
Members in a set are grouped together as one object meaning you do not need to know every member of a set in order to reference it
What other area of logical computer science do sets link in with?
Boolean algebra
What are the two ways of defining a set?
- Listing every member of the set
- Stating the properties that belong to members of the set but not by non-members
Name a common set
- Integers
- Natural numbers
- Rational numbers
- Irrational numbers
- Ordinal numbers
- Real numbers
What does it mean if a common set symbol has a plus or a minus in superscript next to it?
That a further constraint has been applied to the set which is narrowing the field down to just positive or negative numbers
How many empty sets are there?
1
How do you represent an empty set?
{ } or Φ
What does ‘E’ mean?
is a member of
What does ‘E’ with a line through it mean?
is not a member of
What does ‘|’ mean?
such that
What does ‘Λ’ mean?
and
What is the section of the definition following an ‘Λ’ called?
The constraint for and
What does AUB refer to?
All members that are in both A and in B or in A or in B
With does A intersection B refer to?
All members that are in A and in B
What does A\B refer to?
All members that are in A but not in B
What does it mean if A is a subset of B?
Every member of A is also a member of B
What does it mean if A is not a subset of B?
At least one member of A is not a member of B
What is a proper subset?
When one set is a subset of the other but the two sets are not equal to one another
What does it means if A is a proper subset of B?
A is a subset of B but A is not equal to B
What is a cartesian product of two sets?
The set of all ordered pairs from two sets