Formal grammer and relations

• Σ is an alphabet of terminal symbols ({a,b,c,d...})
• disjoint set = mutually exclusive
• In a grammar, N is the set of non-terminal symbols (often A, B) that lead to some other symbol
• S means start
• The grammar itself is a list of pairs (u,w), where u,w = either alphabet or N symbols, repeating any number of times
• a word t is part of a language if, starting with S, it is possible to generate it by repeatedly applying the grammar production rules
• A binary relation between sets X ,Y is a subset R ⊆ X × Y . Abinary relation on X is a subset R ⊆ X × X
• BRs can be reflexive (every a in X is in relation with itself) (∀a ∈ X (a, a) ∈ R)
• BRs can be antireflexive (no a in X is in relation to itself) (∀a ∈ X (a, a) /∈ R)
• BRs can be symmetric (All elements a and b in set X having relation (a,b) are also relations (b,a)) (∀a, b ∈ X (a, b) ∈ R ⇒ (b, a) ∈ R)
• BRs can be anitsymmetric (elements can only be symmetric if they are actually the same element) (∀a, b ∈ X ((a, b) ∈ R ∧ (b, a) ∈ R) ⇒ a = b)
• BRs can be total (For all a and b (including (a,a), either (a,b) must be in relation, or (b,a)) (∀a, b ∈ X (a, b) ∈ R ∨ (b, a) ∈ R)
• Being Total also requires being Reflexive
• BRs can be Transitive (For all a, b, c in X, if (a,b) and (b,c) hold, (a,c) must also hold) (∀a, b, c ∈ X ((a, b) ∈ R ∧ (b, c) ∈ R) ⇒ (a, c) ∈ R)
• Relations are composed Transitively. using X = (R ◦ S) , where R ⊆ A x B and S ⊆ B x C. (a,c) will be in X if (a,b) is in R and (b,c) is in S.
• Transitive closure also = keep doing composition on itself R on R
• Transitive closure is the set of all possible "reachable" nodes/values from all other nodes/values.

  
• Regular languages (right-linear) > Context free > context sensitive > computably enumerable
• Right linear = strictly T → ε or T → aR (strictly one terminal + (optional) one nonterminal)
• Left linear = strictly T -> e or T -> Ra
• right and left linear grammars describe the same languages
• One step derivation relation: → := {(uvw, uv ′w) | u, v , w, v ′ ∈ (Σ ∪ N )* (v , v ′) ∈ R} (uvw is related to uv'w where all "letters" come from the alphabet or nonterm symbols and v' can be generated from v by the rules)
• Language = (double arrow in img) on alphabet = transitive closure of the single step derivation relation = all words reachable from the start symbol with the given rules rules etc.

  
• Context free: the left side of every rule is a nonterminal symbol (R -> a) (does not depend on any terminal symbol (eg. wRa > wra))
• Context sensitive: wAu -> wvu, where MUST be terminal (and not e)
• monotonic: after/for rules u -> w, |u| <= |w| (words can only get longer using rules and never shorter)