PLC Flashcards
Alphabet Notation
Σ 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.
Arity of a symbol?
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.
Parts of a concrete syntax?
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.
Regex Syntax
Syntax of Semantic Rules?
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.
What are the 5 components of a finite automata?
- 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
What is the language of a finite automata?
L(M) = The set of all strings accepted by M
What is the shared trait between Regular Expressions and Finite Automata?
Both express the same set of languages (regular languages)
Pumping Lemma Definition
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
What is the state of an arithmetic expression?
A mapping of variable values to values in Z.
How do you denote a state function?
[x->v]sigma maps x to v in the state sigma.
If the variable x is not defined in the state sigma, what is sigma(x)?
0, by convention
What is A⁻ & A
The set of simple (no variables) arithmetic expressions in While, the set of all arithmetic expressions in While
What is ℬ and B.
ℬ is the set of boolean expressions. B is a variable that represents a specific boolean expression.
What is 𝒮 and S.
𝒮 is the set of statements. S represents a specific statement.
What is the formal definition of Safety?
Finding a subset of all possible States where each state in the subset evaluates to another state when passed to a program.
Difference between partial and total correctness?
Partial Correctness - All executions that terminate are correct
Total Correctness - All executions terminate and are correct
What is a postcondition?
A condition that holds at the end of execution
What is a partial function?
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.
What is a computable function?
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.”
What is the characteristic function of a predicate U?
A function XU(n) that returns 1 if n is in U, and 0 if it is not.
What makes a predicate decidable?
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
What is a semi-characteristic function of a predicate U?
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.
Injections, Surjections, and Bijections
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.
What makes a function an isomorphism?
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.
How do we encode a set of data as natural numbers?
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.
What is a reflection of a function?
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.
What is a Gödel numbering?
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.
What is the universal function?
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.
What is the Church-Turing thesis?
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.
What is the set of Partial Recursive functions?
The set of partial functions on ℕ that are considered computable by any realistic model of computation.
What does e = ⌜ S ⌝ mean?
e is the encoding of the statement S under a Gödel numbering
What is a many-to-one reduction?
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.
What do the up arrows and down arrows mean in reference to a program?
The up arrow means that a program never terminates, a down arrow means it terminates.
What is Rice’s Theorem?
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.
Sum of integers 0 through n inclusive?
(n/2) (n+1)
DFA vs NFA
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.
