4.4 Theory of Computation

Question 1

What is a set in the context of regex

Answer 1

an unordered collection of values in which each value occurs at most once.

Question 2

A language is regular if it can be represented by

Answer 2

1. A regular expression
2. A Finite State Machine

Question 3

If there is no symbol between symbols what does that mean

Answer 3

Members side by side must appear in that sequence

Question 4

What does the pipe symbol mean|

Answer 4

Separates alternative options

Question 5

What does the symbol * mean in context of regex

Answer 5

Indicates that there are zero or more of the preceding element

Question 6

What does the symbol + mean in the context of regex

Answer 6

Indicates that there is one or more of the preceding elements

Question 7

What does the symbol ? mean in the context of regex

Answer 7

Indicates that there are zero or one of the preceding element.

Question 8

What does () symbol mean in the context of regex

Answer 8

Used to identify groupings

Question 9

An 01 pair repeated any number of times

How is it represented in regex

Answer 9

(01)*

Question 10

In the context of set comprehension

A = { x | x ∈ N ^ x != 0 }

define the variables

Answer 10

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”

Question 11

What is a turing machine

Answer 11

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.

Question 12

A⊆B

Answer 12

A is a subset of B

Question 13

A⊂B

Answer 13

A is a proper subset of B

Question 14

Difference between subset and proper subset

Answer 14

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.

Question 15

What is the cartesian product

Answer 15

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)}.

Question 16

What is cardinality and what is denoted by

Answer 16

Cardinality- It represents the count of distinct elements within a set.

|A|

Question 17

In any one transition the turing machine can: (3)

Answer 17

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.

Question 18

What is Backus Nuar Form

What is a meta language

Answer 18

a formal notation used to describe the syntax rules of a language unambiguosly

A language that describes a language

Question 19

Why does Backus Nuar form exist when there are RNF (2)

Answer 19

Because not every language or pattern can be represented as a regular expression

meta-languages such as BNF have been devised

Question 20

In the context of BNF what does this symbol mean ::=

Answer 20

Is defined as

Question 21

In the context of BNF what does this symbol mean |

Answer 21

Or

Question 22

In the context of BNF what does this symbol mean <>

Answer 22

Surrounds category names

Question 23

In the context of BNF what does it mean items are ( Side by side )

Answer 23

they should appear consecutively or in sequence.

Question 24

In the context of BNF what are terminal symbols

Answer 24

basic symbols or literals that appear in the language being defined.

They cannot be broken further down.

Question 25

What are the two ways of representing context free languages

Answer 25

Syntax diagrams

BNF

Question 26

What are syntax diagrams

Answer 26

graphical equivalent of BNF

Question 27

In the context of syntax diagrams what does a rectangle represent

Answer 27

a non terminal symbol, which will be defined in another syntax diagram.

Question 28

In the context of syntax diagrams what does an ellipses represent

Answer 28

a terminal symbol, cannot be further broken down

Question 29

What is a finite state machine (1)

Answer 29

An abstract machine that can be in any one of a finite number of states

Question 30

What are the characteristics of a finite state machine (FSM) (3)

Answer 30

1. Can only be in one state at time.
2. can change from one state to another in response to an event, known as a transition
3. Defined by a list of its states and the conditions for each transition

Question 31

What is a finite state automaton (2)

Answer 31

1. An FSM which has no output is known as a finite state automaton
2. It has a set sequence for the final state

Question 32

What is a mealy machine

Answer 32

1. A type of FSM
2. generates an output on each state transition
3. The output is determined by its current state and its current input.

Question 33

What is the notation used for mealy machine

Answer 33

input/output = 0/1

Question 34

Functions of a mealy machine

Answer 34

1. Can be used to map an input sequence to an output sequence.
2. And it is used in language parsing (language analysis)
3. Can be used to translate from one language to another.

Question 35

In order for source code of a given language to be translated into machine code:

Answer 35

All the rules of a given language must be defined totally ambiguosly

Question 36

What does BNF consist of (3)

Answer 36

A set of terminal symbols
A set of non-terminal symbols
A set of production rules

Question 37

what is the BNF representation for digits

Answer 37

<digit> ::= 0|1|2|3|4|5|6|7|8|9
</digit>

Question 38

If letter has been defined as:

<LETTER> ::= A|B|C|D...etc

How do we define a two letter word
</LETTER>

Answer 38

WORD ::= LETTER >LETTER>

Question 39

What are the applications of regular expressions (3)

Answer 39

Searching and locating files and folders

Find or search and replace text strings in a block of text

Searching for identifiers in a computer program