PLC

Question 1

Alphabet Notation

Answer 1

Σ denotes a generic alphabet.
a,b,c,d stand for the letters.
Empty string is ϵ.
Set of all strings over Σ is Σ*, this always includes the empty string.
For the strings x and y, xy is the result of concatenating them, can be done exponentially too.

Question 2

Arity of a symbol?

Answer 2

How many arguments it takes.

Arity 0 is nullary
Arity 1 is unary
Arity 2 is binary

if a set of symbols is given alongside their arities, they are said to be ranked.

Question 3

Parts of a concrete syntax?

Answer 3

A set of production rules (a.k.a productions, or rules). Each with a head (LHS) and tail (RHS).

Each head consists of a single non-terminal symbol. A rule with a head X is called an X-rule.

The RHS consists of a combination of non-terminal and terminal symbols.

One of the non-terminal symbols is designated as the starting symbol.

Question 4

Regex Syntax

Answer 4

Question 5

Syntax of Semantic Rules?

Answer 5

The hypotheses/premises are placed on top of the line, with the conclusion underneath. The side condition is placed to the right hand side.

If the premises are valid, and the conditions are true, then you can deduce the conclusion is valid.

An instantiation of a rule is when the variables are replaced with specific instances of the correct type.

Question 6

What are the 5 components of a finite automata?

Answer 6

• A collection of states Q
• A finite alphabet Sigma
• A transition function sigma of type Q X Sigma -> Q
• An initial state q0 which is an element of Q
• A collection of accepting states F which is a subset of Q

Question 7

What is the language of a finite automata?

Answer 7

L(M) = The set of all strings accepted by M

Question 8

What is the shared trait between Regular Expressions and Finite Automata?

Answer 8

Both express the same set of languages (regular languages)

Question 9

Pumping Lemma Definition

Answer 9

For any regular language:

There is a natural number p such that for any word of length at least p, the word can be split into three parts u,v,w such that:

• v is not empty
• |uv| <= p
• for any integer i u(v^i)w is in the language

Question 10

What is the state of an arithmetic expression?

Answer 10

A mapping of variable values to values in Z.

Question 11

How do you denote a state function?

Answer 11

[x->v]sigma maps x to v in the state sigma.

Question 12

If the variable x is not defined in the state sigma, what is sigma(x)?

Answer 12

0, by convention

Question 13

What is A⁻ & A

Answer 13

The set of simple (no variables) arithmetic expressions in While, the set of all arithmetic expressions in While

Question 14

What is ℬ and B.

Answer 14

ℬ is the set of boolean expressions. B is a variable that represents a specific boolean expression.

Question 15

What is 𝒮 and S.

Answer 15

𝒮 is the set of statements. S represents a specific statement.

Question 16

What is the formal definition of Safety?

Answer 16

Finding a subset of all possible States where each state in the subset evaluates to another state when passed to a program.

Question 17

Difference between partial and total correctness?

Answer 17

Partial Correctness - All executions that terminate are correct
Total Correctness - All executions terminate and are correct

Question 18

What is a postcondition?

Answer 18

A condition that holds at the end of execution

Question 19

What is a partial function?

Answer 19

A function that might not have an output for every input. Denoted with ⇀ e.g. f : ℕ ⇀ ℕ.

The function computed by a while program must be partial because while programs may infinitely loop on some inputs.

Question 20

What is a computable function?

Answer 20

A function F is computable if there is a while program that computes F with respect to the variable x. “with respect to” is often abbreviated to “wrt.”

Question 21

What is the characteristic function of a predicate U?

Answer 21

A function XU(n) that returns 1 if n is in U, and 0 if it is not.

Question 22

What makes a predicate decidable?

Answer 22

A predicate U ⊆ ℕ is decidable just if its characteristic function is computable, if it not computable then the predicate is undecidable.

The while program that computes the characteristic function is called a decision procedure

Question 23

What is a semi-characteristic function of a predicate U?

Answer 23

A function ξU(n) that returns 1 if n is in U, and is undefined if it is not.

The idea is that semi-characteristic functions are easier to compute since the program does not need to terminate on ns that aren’t in U.

A predicate is semi-decidable just if its semi-characteristic function is computable.

Question 24

Injections, Surjections, and Bijections

Answer 24

Injective functions are 1-1 mappings. If f(a1) == f(a2) then a1==a2.
f : A ↣ B

Surjective functions are functions where every element in the output set has a corresponding element in the input set.
f : A ↠ B

A function is a bijection if it is both Injective and Surjective.

Question 25

What makes a function an isomorphism?

Answer 25

A function f : A → B is an isomorphism just if it has an inverse.

A function is a bijection if and only if it is an isomorphism.

Question 26

How do we encode a set of data as natural numbers?

Answer 26

Create a bijection between them. We usually end up using a pairing function (a function that maps NxN -> N) as the base of this bijection.

Question 27

What is a reflection of a function?

Answer 27

The function f: A ⇀ A has a reflection f̃: ℕ ⇀ ℕ which converts the input from ℕ to A, runs it through f and then converts that output to ℕ. It uses a provided bijection/encoding to do so: i : A ⇀ ℕ

This can also be done with functions with a different domain and codomain by using a different bijection for the domain and codomain.

Question 28

What is a Gödel numbering?

Answer 28

An encoding of a system within itself. They can be used to represent While programs as natural numbers, allowing us to write While programs that handle other While programs.

Question 29

What is the universal function?

Answer 29

A function that can produce the behaviour of every computable function.

U : Stmt × ℕ ⇀ ℕ
U(P, n) = ⟦ P ⟧(n)

That is it outputs the result of running the program P with the input n. U is partial because the computable functions themselves are partial.

The existence of this function allows for the writing of an interpreter, in the form of a program which reads in each statement in the program, simulates it, and continues to the next line.

Question 30

What is the Church-Turing thesis?

Answer 30

Any two models of computation are equivalent with respect to the computability of functions ℕ ⇀ ℕ.

This means an interpreter can be written in any model of computation for any other model of computation.

Question 31

What is the set of Partial Recursive functions?

Answer 31

The set of partial functions on ℕ that are considered computable by any realistic model of computation.

Question 32

What does e = ⌜ S ⌝ mean?

Answer 32

e is the encoding of the statement S under a Gödel numbering

Question 33

What is a many-to-one reduction?

Answer 33

Let U,V be predicates in ℕ. Let f : ℕ → ℕ. The function f is a many-to-one reduction from U to V just if:

• it is computable, and
• n ∈ U ⟺ f(n) ∈ V

We may sometimes write f : U ≲ V to mean f is a reduction from U to V

If U reduces to V and V is decidable, then so is U. Contrapositively: if U is undecidable, so is V.

Question 34

What do the up arrows and down arrows mean in reference to a program?

Answer 34

The up arrow means that a program never terminates, a down arrow means it terminates.

Question 35

What is Rice’s Theorem?

Answer 35

For any subset of PR (all computable functions), that isn’t trivial (all/no functions), the reflected set is undecidable. That is to say if we have a subset of PR (e.g functions that return a zero) asking if a function is part of that set is not necessarily possible. We may not be able to tell, or we might get the answer wrong.

Question 36

Sum of integers 0 through n inclusive?

Answer 36

(n/2) (n+1)

Question 37

DFA vs NFA

Answer 37

An NFA (non-deterministic finite automata) can have multiple transitions from the same state for the same character. Usually used to represent systems with multiple workers computing at the same time.