Cs374 Lecture 2

Powers of Languages

L^i = L * L^{i-1}

Max elements of languages ^ i is len(L) ^ i

Kleene star = $L^{*} = L^{i},\forall i\in \mathbb{N}$

Important is that you can go from finite to infinite languages.

the empty string is a part of any language which is applied the Klneene start operator.

Strings are always finite length. Countably many strings but uncountably many languages.

Because of this fact, there are languages that cannot be computed. (is this where)

$L^+ = L^{*} - {\epsilon}$ if $\epsilon$ is not in $L$

Regular Languages are all languages obtainable from union, concat, and star, where you apply then a finite number of times, starting from trivial base case.

Formal proof: Start from basic base cases, Regular lanague if $L_1$, $L_2$ are regular then so are $L_1 \cup L_2$, L_1L_2, and L^*

All finite languages are regular,

Some infinite languages are not regular, regular languages are languages that have some reuglar pattern. You cannot difference.

Notation for regular expressions:

All regular languages have regular expressions, but all regular languages can have multiple expressions. Regular expressions are shorthand for languages while L(r) mean a langauge corresponding to expression r.

(01+1)(0+1)^*