Theory of Computation / Regular Languages

What is a finite state machine?

An abstract representation of how something changes from one state to another

What is a finite state machine with no output called?

A finite state automaton

What is a mealy machine?

A type of finite state machine which generates an output on each state transition

What is a set?

A well-defined collection of objects

What 2 qualities does a set have?

1) A set must be unordered

2) Each member in a set can only occur once

What are the 3 set operations, what are their symbols and what do they mean?

1) Union, A ∪ B, The set all members that are in A or B or both

2) Intersection, A ∩ B, The set of all members in both A and B

3) Difference, A \ B, The set of all members that are in A but not in B

What is a subset and what is its symbol?

Every member of the subset is a member of the superset, A ⊆ B (A is a subset of B)

What is a proper subset and what is its symbol?

Every member of the subset is a member of the superset and the two sets are not the same, A ⊂ B (A is a proper subset of B)

What is the Cartesian product of two sets?

The set of all ordered pairs (a, b), such a ∈ A and b ∈ B

What is the cardinality of a set and how is it denoted?

The number of elements in a set, |A|

What is a countably infinite set?

One whose members can be counted using the infinite set N

What is the symbol for an empty set?

Ø

What are regular expressions?

Patterns used to specify a set of strings. They are simple ways of describing a set

What are the 5 bits of notation for a regular expression?

1) | separates alternatives (or, V)

2) * indicates that there are zero or more of the preceding element

3) + indicates that there is one or more of the preceding element

4) ? indicates that there are zero or one of the preceding element

5) () used to identify groupings

What is a regular language?

A language that can be represented by a regular expression

What is a context-free language?

A language that cannot be expressed by regular expressions

What can be used to represent context-free languages?

Backus-Naur Form

What is Backus-Naur Form?

A meta-language, a language that describes a language

What 3 bits of notation are used in Backus-Naur Form?

1) ::= Is defined as

2) | Or

3) <> Surrounds category names

What can a Turing machine be viewed as?

A computer with a single fixed program

What is a Turing machine expressed using? (4 things)

1) A finite set of states

2) A finite alphabet of symbols

3) An infinite tape with marks of squares

4) A sensing read-write head that can travel along the tape

What is the controller in a Turing machine?

A finite state machine which tells the machine what to do next

What 3 things can the controller do in a Turing machine in every transition?

1) Read the symbol on the tape

2) Erase or write a new symbol on the tape

3) Move the head left or right by a single space

What are syntax diagrams?

Another way to represent context-free langues. It is the graphical equivalent of Backus-Naur Form

What is infix notation?

The notation used to represent arithmetic and logcal statements as we usually interpret them (eg 4 + 7)

What prefix / Polish notation?

Operation are placed before the operands (eg + 4 7)

What is postfix / Reverse Polish Notation?

Operators follow their operands (eg 4 7 +)

Why should you use Reverse Polish Notation?

Eliminates the need for brackets and is easier for the computer to process

What data structure can be used to evaluate an expression in Reverse Polish Notation?

A stack

What is a Universal Turing Machine?

A Turing machine that can simulate the behaviour of any other Turing machine. It faithfully executes the instructions and data on the simulated machine

Why are Universal Turing Machines considered more powerful than computers today?

They have an infinite amount of memory/tape

What is the Halting Problem?

The problem of determining for a given input, whether a program will finish running or continue forever

What is the significance of the Halting problem?

It shows that there are some problems that can never be solved by computers