Algebra
Popular posts from this blog
Sets
Basic properties of sets Two characteristics of a set There are no repeated occurrences of elements There is no particular order or arrangement of the elements How do you show A is a subset of B? If A and B are sets and every element of A is also an element of B, then A is a subset of B. How do you show A = B? A is a subset of B, and B is a subset of A Operations on sets Union - A union B = set of x s.t. x is an element of A or x is an element of B Intersection - A intersect B = set of x s.t. x is an element of A and x is an element of B Complement Cardinality Inclusion-Exclusion principle | A ∪ B | = | A | + | B | − | A ∩ B |. Inclusion-Exclusion for 3 sets | A ∪ B ∪ C | = | A | + | B | + | C | − | B ∩ C | − | A ∩ B | − | A ∩ C | + | A ∩ B ∩ C | Difference rule | A − B | = | A | − | A ∩ B |.
Grammars
Structure of grammar L is a language over an alphabet A then a grammar for L α → β α = strings of symbols taken from language A β = strings of symbols from a grammar disjoint from A. Can be interpreted as: replace α by β α produces β α rewrites β α reduces β --- Start symbol S → β Ex. Let A = { a, b, c }. S → Λ | aS | bS | cS Ex. Set of binary numerals that represent odd numbers O → B 1 B → Λ | B 0 | B 1. --- S → AB A → Λ | aA B → Λ | bB. Leftmost derivation S ⇒ AB ⇒ aAB ⇒ aaAB ⇒ aaB ⇒ aabB ⇒ aab . Rightmost Derivation S ⇒ AB ⇒ AbB ⇒ Ab ⇒ aAb ⇒ aaAb ⇒ aab . --- The Language of a Grammar (3.3.4) If G is a grammar with the start symbol S and the set of terminals T , then the language of G is the set L ( G ) = { s | s ∈...
Comments
Post a Comment