Skip to main content

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 (sigma) Σ1=a,b,c\Sigma_{1}={a,b,c}

Σ\Sigma^* is the same as List Σ\Sigma in lean

LΣL \in \Sigma^** (language in set) Also saying L is a predicate

Operations on Languages

Other notes

Inductive Definition - All the ways elements on Σ\Sigma^* can be defined. Kleene star/operator/closure - Unary *-operator Only write \in when on its own

\in - Denotes the empty word, a sequence of symbols of length 0 ∅ - Denotes the empty set, a set with no elements {\in} - Is a set with exactly one element 0 the empty word

Can use exponent notation to denote concatenation of a word with itself. u2=uuu^2 = uu. u0=u^0 = \in