Unit 9 - Regular Languages

Question 1

What is a mealy machine?

Answer 1

A mealy machine is a FSM which has an output determined by its current state and current input.

Question 2

What is a state transition table?

Answer 2

A state transition table may be used to define a Mealy machine or a Turing machine. It shows all the states and possible inputs and the outputs for each combination of state and input.

Question 3

What is a set?

Answer 3

A set is a well-defined collection of objects.
- Objects in the set are members or elements,
- A set is unordered,
- Each member in a set can only occur once,
- A set is usually denoted by a capital letter,
- A member is usually denoted by a lower case letter.
- A set can be defined by listing every member,
- A set can be defined by stating the properties held by the members, but not by the non-members,
- The members are enclosed by { } and separated by a comma.

Question 4

What are the common sets?

Answer 4

• N = set of natural numbers: 0, 1, 2,…
• P = set of positive integers: 1, 2, 3,…
• Z = set of all integers: …, -2, -1, 0, 1, 2, …
• Q = set of rational numbers (can be expressed as a fraction)
• R = set of real numbers

These set names may be shown as bold letters or in a special font

Question 5

What are the set membership expressions?

Answer 5

• If S is a set, then the expression
  x ∈ S
  means
  “x is a member of the set S”
• The expression
  x ∉S
  means
  “x is not a member of the set S”

Question 6

What is the notation for set comprehension?

Answer 6

• such that: |
• x is a member of the set of N (natural numbers {0, 1, 2, …}): x ∈ N
• and: ^
• Set comprehension: S = { x | x ∈ N ᴧ x is even }
• Compact representation: S = { x ∈ N | x is even }
• Compact representation for strings: T = { 0n1n | n ≥ 1 } = {01, 0011, 000111, …}

Question 7

What are set operations?

Answer 7

• Union: A ∪ B is the set of all members that are in A or in B,
• Intersection: A ∩ B is the set of all members in both A and B,
• Difference: A \ B is the set of all members that are in A but not in B.

Question 8

How might the empty set be represented?

Answer 8

{} or ø

Question 9

What are the rules for subsets?

Answer 9

• A is a subset of B, when every member of A is also a member of B:
• A ⊆ B
• A is not a subset of B, if at least one member of A does not belong to B :
• A ⊈ B
• A is a proper subset of B, when A is a subset of B but A ≠ B:
• A ⊂ B

Question 10

What is the cartesian product of two sets?

Answer 10

The Cartesian product of two sets A and B is the set of all ordered pairs (a, b), such that a ∈ A and b ∈ B
Cartesian product notation: A x B, read as “A cross B”

Question 11

What is a finite set?

Answer 11

A finite set contains an exact number of distinct members where number ∈ N.

Question 12

What is the cardinality of a set?

Answer 12

The cardinality of a finite set is the number of members in the set.

Question 13

What is an infinite set?

Answer 13

An infinite set contains an infinite number of distinct members.

Question 14

What is a regular expressions?

Answer 14

Regular expressions are patterns used to specify a set of strings.
- A simple way of describing a set,
- A way of describing some types of languages using a shorthand notation.

Question 14

What is a countably infinite set?

Answer 14

A countably infinite set is one whose members can be counted using the infinite set N.

Question 15

What are the notation rules for regular expressions?

Answer 15

• Members side-by-side must appear in that sequence,
• | : Separates alternatives (or, ⋁),
• asterisk : Indicates that there are zero or more of the preceding element,
• plus : Indicates that there are one or more of the preceding element,
• ? : Indicates that there are zero or one of the preceding element,
• () : Used to identify groupings.

Question 16

What is a regular language?

Answer 16

A language is regular if it can be represented by a regular expression or finite state machine (FSM).

Question 17

What is a Turing machine?

Answer 17

A Turing machine is a theoretical machine, rather than a physical object, thought up by Turing in 1936 which can simulate ANY computer algorithm, no matter how complex.

A Turing Machine consists of two parts: the tape that the machine can read and write, and the controller (the program) determines what happens at each cell.
- It has a read-write head that can read symbols from the tape,
- The tape is infinitely long, with marked-off squares,
- The machine must have at least one state, the halting state, that causes it to halt for some inputs.

Question 18

What is a controller?

Answer 18

The “controller” is a finite state machine which tells a Turing machine what to do next.

Question 19

What is a transition function?

Answer 19

A transition function is a way to represent the transition arc between two states on a state transition diagram.
- The symbol δ is the lower case Greek letter delta: it means a small change
- Each transition arc on a state transition diagram can be represented by the δ function using a pattern:
δ (Current state, Input symbol) = (Next state, Output symbol, Head move)

Question 20

Why is the Turing Machine important?

Answer 20

• It provides a definition of what is computable,
• It can be proven mathematically that a Turing Machine is capable of computing anything that is computable,
• The mathematical definition of a Turing machine defines what is computable.

Question 21

What is a Universal Turing Machine?

Answer 21

A Universal Turing Machine simulates the behaviour of any Turing machine by reading the definition of a Turing machine and the input data.
This led to the idea of the stored program computer and specifically Von Neumann architecture.

Question 22

Why is the Universal Turing Machine important?

Answer 22

• It provides a definition of what is computable,
• It can be proven mathematically that a Universal Turing Machine is capable of computing anything that is computable.

Question 23

What are the four characteristics of a Turing machine?

Answer 23

1. A finite set of states,
2. A finite alphabet of symbols,
3. An infinite tape, marked off in squares,
4. A read-write head that can move left and right one square at a time.

Question 24

What is the relationship between a transition function and a state transition diagram?

Answer 24

The transition function can be used to produce the same rules for transitions as illustrated on a state transition diagram. This provides for a more compact definition which can be manipulated mathematically.

Question 25

Why can a Universal Turing machine can be considered an interpreter?

Answer 25

Because a UTM simulates the behaviour of a TM. A UTM interprets the definition of the TM (its transition functions) and applies them to the TM’s input.

Question 26

What is Backus-Naur Form?

Answer 26

Backus-Naur Form (BNF) is the formal notation used to describe the syntax rules of a language, it’s a meta-language: A language that describes a language.

Question 27

Why do we need BNF?

Answer 27

Regular languages are expressible by regular expressions, but some languages cannot be expressed by a regular expression. The class of languages called context-free languages is more expressive than regular languages. BNF is a way to define these context-free languages.

Question 28

What are the BNF meta-symbols?

Answer 28

- ::= : Is defined as, - | : OR, - < > : Surrounds category names, - Side by side: Items must follow exactly, - Terminal symbols: Cannot be further broken down, - Non-terminal symbols: Can be further broken down.

Question 29

How can a context free language be defined by BNF?

Answer 29

A context-free language can be defined by BNF when a single non-terminal symbol on the left can always be replaced by the definition on the right.

Question 30

What is a production rule?

Answer 30

Each individual BNF statement is called a ‘production rule’.

Question 31

What is a recursive rule?

Answer 31

A recursive rule is defined in terms of itself.

Question 32

What is parsing?

Answer 32

The act of parsing is checking an input string against the set of BNF rules to see if it is valid.

Question 33

What is a parse tree?

Answer 33

A graphical way to represent parsing.

Question 34

What is a syntax diagram?

Answer 34

Another way to represent context-free languages, it is the graphical equivalent of BNF.

Question 35

What is Prefix notation?

Answer 35

The operator comes before the operands. Also known as Polish notation. / * a + b c d [Infix: a * (b + c) / d]

Question 36

What is Infix notation?

Answer 36

The operator comes between the operands. This is the notation used in the mathematics you’ve encountered before . a * (b + c) / d

Question 37

What is Postfix notation?

Answer 37

The operator comes after the operands. Also known as Reverse Polish notation. a b c + * d / [Infix: a * (b + c) / d]

Question 38

Why was Reverse Polish notation (RPN) / Postfix notation invented?

Answer 38

Reverse Polish was devised as a way to do mathematics without braces. The system is used extensively in computer algorithms because evaluation can be done using a stack.

Question 39

Why use Reverse Polish notation (RPN) / Postfix notation?

Answer 39

- Eliminates the need for brackets in sub-expressions, - The resulting expressions can be evaluated using a stack (more later), - Used in interpreters based on a stack.

Question 40

What is the arithmetic order of precedence?

Answer 40

1. ~ - unary minus, 2. ^ - exponentiation, 3. * / - multiplication and division, 4. + - - addition and subtraction, 5. = - equals

Question 41

What are the ways to convert from infix to RPN?

Answer 41

- Translation by numbering, - Translation by bracketing, - Translation by binary tree.

Question 42

What are the ways to convert from RPN to infix?

Answer 42

- Translation by scanning, - Translation by bracketing.

Question 43

How does Translation by numbering work?

Answer 43

This algorithm works by numbering operands and operators: 1) Start on left, with the number 1, 2) If the token is an operand, allocate the next number, 3) Ignore brackets except in so far as they affect the order of calculation, 4) If it is an operator, and enough operands are available, then back up and number the operator, otherwise advance to next token, 5) Keep order of precedence in mind, as it might require some reading ahead, 6) When finished, write down the tokens in numerical order.

Question 44

How does Translation by bracketing (Infix to RPN) work?

Answer 44

This method works by fully bracketing the expression and rearranging the operators inside the brackets: 1) Add brackets to fully enforce order of precedence, including exponentiation, 2) Move the operator in each set of brackets to the end position, 3) Remove all the brackets.

Question 45

How does Translation by binary tree work?

Answer 45

This method works by building a binary tree from the infix expression and then traversing it using a post-order traversal algorithm. e.g. a * (b + c) / d 1) Decompose operands into two child nodes; pay attention to precedence and brackets, 2) Repeat these two steps until you have a tree.

Question 46

How does Translation by Scanning work?

Answer 46

This method works by scanning left to right, picking out pairs of operands and single operators: 1) Scan right, writing down operands, 2) If you find an operator, check if you have already written operands where it can be inserted, 3) If inserting an operator, add brackets

Question 47

How does Translation by bracketing (RPN to Infix) work?

Answer 47

This method works by adding brackets to enforce order of execution, then moving operators between operands. 1) Insert brackets as indicated by operators, 2) Move operators between closest operands, 3) Remove excess brackets.