4.4 Theory of Computation Flashcards
What is a set in the context of regex
an unordered collection of values in which each value occurs at most once.
A language is regular if it can be represented by
- A regular expression
- A Finite State Machine
What does a.e mean in regex
Matches any word that starts with a and ends with e
what does ^Hello mean
Matches any line that starts with Hello
What are regular expressions
Special sequences of characters that can be used to find or match patterns in text
If there is no symbol between symbols what does that mean
Members side by side must appear in that sequence
What does the pipe symbol mean|
Separates alternative options
What does the symbol * mean in context of regex
Indicates that there are zero or more of the preceding element
What does the symbol + mean in the context of regex
Indicates that there is one or more of the preceding elements
What does the symbol ? mean in the context of regex
Indicates that there are zero or one of the preceding element.
What does () symbol mean in the context of regex
Used to identify groupings
An 01 pair repeated any number of times
How is it represented in regex
(01)*
In the context of set comprehension
A = { x | x ∈ N ^ x != 0 }
define the variables
A represents the set
{}: This denotes a set. Sets are collections of distinct elements.
x: A variable that represents the elements of the set.
∣: The vertical bar is read as “such that” or “where”. separates the variable from the condition that the elements must satisfy.
natural numbers (N)
∈ = “is an element of”
What is a turing machine
A computer with a single fixed program expressed using:
A finite set of states in a state transition diagram.
A finite alphabet of symbols.
An infinite tape with marked off squares.
A sensing read-write head that can travel along the tape, one square at a time.
A⊆B
A is a subset of B
A⊂B
A is a proper subset of B
Difference between subset and proper subset
A is a proper subset of B if every element in A is also in B, but B has at least one extra element not in A
A normal subset does’nt have to satisfy this last condition.
What is the cartesian product
The cartesian product of two sets A and B is the set of all ordered pairs (a,b)
Let’s say A = {1, 2} and B = {x, y}.
The Cartesian product of A and B would be {(1, x), (1, y), (2, x), (2, y)}.
What is cardinality and what is denoted by
Cardinality- It represents the count of distinct elements within a set.
|A|
In any one transition the turing machine can: (3)
Read the symbol on the tape.
Erase or write a new symbol on the tape.
Move the head left or right by a single machine.
What is Backus Nuar Form
What is a meta language
a formal notation used to describe the syntax rules of a language unambiguosly
A language that describes a language
Why does Backus Nuar form exist when there are RNF (2)
Because not every language or pattern can be represented as a regular expression
meta-languages such as BNF have been devised
In the context of BNF what does this symbol mean ::=
Is defined as
In the context of BNF what does this symbol mean |
Or
In the context of BNF what does this symbol mean <>
Surrounds category names
In the context of BNF what does it mean items are ( Side by side )
they should appear consecutively or in sequence.
In the context of BNF what are terminal symbols
basic symbols or literals that appear in the language being defined.
They cannot be broken further down.
What are the two ways of representing context free languages
Syntax diagrams
BNF
What are syntax diagrams
graphical equivalent of BNF
In the context of syntax diagrams what does a rectangle represent
a non terminal symbol, which will be defined in another syntax diagram.
In the context of syntax diagrams what does an ellipses represent
a terminal symbol, cannot be further broken down
What is a finite state machine (1)
An abstract machine that can be in any one of a finite number of states
What are the characteristics of a finite state machine (FSM) (3)
- Can only be in one state at time.
- can change from one state to another in response to an event, known as a transition
- Defined by a list of its states and the conditions for each transition
What is a finite state automaton (2)
- An FSM which has no output is known as a finite state automaton
- It has a set sequence for the final state
What is a mealy machine
- A type of FSM
- generates an output on each state transition
- The output is determined by its current state and its current input.
What is the notation used for mealy machine
input/output = 0/1
Functions of a mealy machine
- Can be used to map an input sequence to an output sequence.
- And it is used in language parsing (language analysis)
- Can be used to translate from one language to another.
In order for source code of a given language to be translated into machine code:
All the rules of a given language must be defined totally ambiguosly
What does BNF consist of (3)
A set of terminal symbols
A set of non-terminal symbols
A set of production rules
what is the BNF representation for digits
<digit> ::= 0|1|2|3|4|5|6|7|8|9
</digit>
If letter has been defined as:
<LETTER> ::= A|B|C|D...etc
How do we define a two letter word
</LETTER>
WORD ::= <LETTER> <LETTER></LETTER></LETTER>
What are the applications of regular expressions (3)
Searching and locating files and folders
Find or search and replace text strings in a block of text
Input validation
What is procedural abstraction
Procedural abstraction is a programming concept that involves breaking down complex tasks into smaller, reusable procedures
What is functional abstraction
Same as procedural abstraction, but whilst ignoring the internal computation and simply outputting the result
What is data abstraction
hiding the implementation details of data structures and exposing only the essential features
What is problem abstraction
Removing details from a problem until you can represent it in a way that it is possible to solve, as you reduce it to one that has already been solved.
What is procedural/problem decomposition
The process of taking a large problem and breaking it down into several smaller problems
What is composition abstraction
Combining of appropriate procedures to form compound procedures
What is automation
use of computational thinking and programming to create systems that perform tasks automatically without human intervention
What is a finite state machine in logical terms
A model of computation used to design computer programs
What does the set of values denoted by N represent
Infinite set of natural number
What does the set of values denoted by Z represent
Set of all integers
What does the set of values denoted by Q represent
Set of all rational numbers
What does the set of values by R represent
Set of all real numbers
What is meant by an infinite set
A set that has no end value represented by … at the end of the set
What does it mean if a set is countable
A set that can be counted off against a subset of the natural numbers
What is a subset
When every member of set is A is also a member of Set B this is a
subset
What is a proper subset
If every member of A is in B, but b has additional values not in A, therefore A and B are not equal,
The A is a proper subset of B
What does A/B mean in regex
Everything that is in set A but not in set B
Which symbol represents “is an element of”
∈
What is parsing
Parsing is the process of analysing a sequence of symbols (such as text or code) to determine its grammatical structure based on a given set of rules (syntax)
What is parsing in the context of BNF
Working out if a statement is valid according to BNF production rules
What is meant by time complexity
How much time an algoritihm needs to solve a given problem
What is meant by space complexity
The amount of memory an algorithim requires to solve a given problem
What is meant by the permutation of a set of objects
The number of ways you can arrange those objects
what is meant by the domain, range and codomain of a function
Domain is All the possible inputs of a function
Codomain is what the function could output (defined by the function).
Range is what the function actually outputs.
What is meant by O(n) linear complexity
An algorithm whose performance is proportional to the size of the data set, where performance declines as the data set grows
What is meant by O(logn) linear complexity
An algorithm that halves the data set in each pass, making it efficient for large data sets
What is meant by the halting problem
Is it possible to write a program that given a description of another program and its inputs without executing the program, whether the given problem will halt.§
What is the universal turing machine
a single machine that can be used to compute any computable sequence.
special type of Turing machine that can simulate any other Turing machine
