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.
