This section will be about strings, languages and language operations. You can find the related notes here.

Definitions and Properties

I first introduce what we mean by a string and a language in the context of theoretical computer science. I provide some common properties of these objects that will re-occur throughout the course.

Operations on languages

Much like sets, languages also have associated operations. I discuss some of these along with some exercises. Extra exercises are at the end of the handout for you to practice!


Exercise (Sipser). Prove that \(L^2 \subseteq L\) iff \(L = L^+\). This is a good exercise to both practice your proving skills and get familiar with language operations.

Exercise. Suppose \(A\) and \(B\) are two languages defined over a non-empty alphabet \(\Sigma\). Prove that if both languages are finite \(|A \times B| = |A| \times |B|\). Is the same true for language concatenation?