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
Define cardinality
The number of elements in a finite set
What is the notation for cardinality?
’| <set> |'</set>
Define regular expression
A pattern used to identify sets of string
How are regular expressions linked to sets?
Regular expressions act as set definitions and these sets are the acceptable strings for that language
What does ‘|’ mean in regular expressions?
Or
What does ‘*’ mean in regular expressions?
There are 0 or more of the preceding element
What does ‘+’ mean in regular expressions?
There is 1 or more of the preceding element
What does ‘?’ mean in regular expressions?
There is 1 or 0 of the preceding element
What does ‘()’ mean in regular expressions?
The characters within the brackets act as one element and are grouped together
What makes a language regular?
If it can be expressed by a regular expression and a FSM
How do regular expressions translate to FSMs?
The characters acts as state transitions and each time a character is inputted the FSM will change state based on the rules of the regular expression. If the FSM is in the accept state at the end of the string then the string meets the rules of the regular expression.
Define Turing machine
A general model of computation that can be defined to represent any computation
What is a Turing Machine (in words not definitions)?
It is a thought experiment derived by Alan Turing that consists of a theoretical machine that can carry out any computer algorithm no matter how complex it was
Why did Alan Turing think of the Turing Machine?
He was attempting to define computability and determine what was mathematically computable
What 4 elements make up the program for a TM?
- A finite set of states in a state transition diagram
- A finite alphabet of symbols
- An infinite tape of marked off squares
- A sensing read/write head that can travel along the tape in either direction one square at a time
What are the two parts of the machine in the TM?
The controller and the tape
What does the controller in a TM do?
The controller decides what happens at each cell on the tape
What other model of computation is the controller in a TM?
A mealy machine
What 3 actions can the TM perform for each transition?
- Read the symbol on the tape
- Erase and write a new symbol on the tape
- Move the head left or right a single space
What are the 3 parameters for the Mealy machine transitions that is the controller in the TM?
- The input
- The output
- The direction of movement
What is a transition function?
A method of representing the transition arc between two states in a state transition diagram
What symbol represents a transition function?
δ
What is the format of a transition function?
δ (<current>, <input></input>) = (<next>, <output>)</output></next></current>
What is the difference between a TM and UTM?
A UTM takes an additional input which is the program (aka the controller) so it can perform a range of different function
What element of von Neumann’s architecture was inspired by the UTM?
The stored program concept
What was the significance of the TM?
It provides a definition of what is computable and it can be mathematically proven that a TM is capable of computing anything that is computable
What does BNF stand for?
Backus-Naur Form
Define BNF
A formal notation used to describe the syntax rules of a programming language
What type of language is BNF?
A meta-language
Define meta-language
A language that describes a language
Define context free language
An unambiguous way of describing the syntax of a language
When are context free languages used?
When the syntax of a language is complex
Why would you choose a context free language over regular expressions to describe syntax rules?
Regular expressions only work when there is a finite limit on the number of ways something can be organised and do not work for more complex languages
Define terminal in terms of BNF
The final element that requires no further rules (cannot be broken down any further)
What does ::= mean in BNF?
is defined as
What does | mean in BNF?
or
What does <> mean in BNF?
Surrounds category names
Why is BNF used to represent programming languages?
Programming languages require strict and precise rules which can be represented by BNF syntax
Define production rule
A single BNF statement
What does it mean if a production rule is recursive?
The production rule calls itself and should be iterated through until the ‘stopping condition’ is reached and it does not call itself
Define syntax diagram
A method of visualising rules written in BNF or other context free languages (one syntax diagram represents one production rule)
Define reverse polish notation (RPN)
Another term for postfix notation
What word describes the way in which we write mathematical expressions?
Infix notation
Define prefix
Expressions that are written with the operators before the operands .e.g. + 2 3
Define postfix
Expressions that are written with the operators after the operands .e.g. 2 3 +
Define polish notation
Another way of describing prefix notation
Why was polish notation created?
It was a simpler way of writing expressions that removed the need for brackets completely whilst still maintaining no ambiguity about how the expression should be executed
Why polish notation adapted to become reverse polish notation?
It was a way of writing expressions that were in a convenient format for an interpreter to understand whilst translating lines of code
Why is RPN more beneficial for interpreters?
An interpreter analyses operands first and then the operators so the operators should be on the right hand side of the expression
What ADT is used to evaluate RPN expressions?
A stack
Define in-order traversal
A method of extracting data from a binary tree that will result in an infix expressions
Define post-order traversal
A method of extracting data from a binary tree that will result in a postfix expression
Define pre-order traversal
A method of extracting data from a binary tree that will result in a prefix expression
