Ordered Structures

Basic Properties of:

  • Tuples
    • What are the two characteristics of a tuple?
    • Product rule to count tuples
    • Cartesian product A x B
  • Lists
    • Difference from tuples
  • Strings
  • Languages
  • Relations
Language
What is the product LM of two languages L and M?

If A is an alphabet, what is A*?

What is a relation, binary relation

---
Regular Expression

Comments

Post a Comment

Popular posts from this blog

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 ∈ T * and S ⇒ + s }. Three simple grammars 1. {Λ, a, aa , …, a n , … } = { a n | n ∈ N}. • S → Λ | aS . 2. {Λ, ab, aabb , …, a n b n , … } = { a n b n
Read more