1. Language
02/02/23
Example Languages L1: Binary sequences representing binary numbers (no leading 0s) L2: Binary sequences representing prime numbers L3: Sequence of a,b with the same number of a's b's L4: Sequences of a,b with the same number of a's and b's MOD 2 L5: Sequences of '(' , ')' match with brackets match L6: Sequences of characters representing valid C programs L7: Sequences of characters of the form code, arg where code is a valid C program, def a function f st. f("arg") terminates L8: Sequences over a,b,c which are either in the set {ab,ac,abc} -> finite language
(Dan Terms) - Language is a set of rules which need to be followed for it to become valid
Definition
A language is a set of words (produces own words) word - sequence of symbols symbols - an element of an alphabet alphabet - a finite set (or type)
(sigma)
is the same as List in lean
(language in set) Also saying L is a predicate
Operations on Languages
Other notes
Inductive Definition - All the ways elements on can be defined. Kleene star/operator/closure - Unary *-operator Only write when on its own
- Denotes the empty word, a sequence of symbols of length 0 ∅ - Denotes the empty set, a set with no elements {} - Is a set with exactly one element 0 the empty word
Can use exponent notation to denote concatenation of a word with itself. .