Formal Languages

Notations are borrowed from [[Set Theory]]

def. $\Sigma$ is the set of all symbols

def. A string is a finite set of symbols

def. A language is a set of strings

String Manipulation §

• $\lambda$ is the empty string
• $\text{concat}(w,v)=w\circ v=wv$
  • …naturally, $w^n=w\cdots w$
• $\text{reverse}(w)=w^R$
• $\text{len}(w)=|w|$

---

We can also define languages as containing strings. Some common ones:

• ${\Sigma }^{\ast }$ ← set of strings, which are concatenated symbols 0 or more times
• ${\Sigma }^{+}$← set of strings, which are concatenated symbols 1 or more times

\Sigma=\{a,b\}. Then:

• ${\Sigma }^{\ast }=\{\lambda ,a,b,aa,ab,ba,bb,...\}$
• ${\Sigma }^{+}=\{a,b,aa,ab,ba,bb,...\}$

You can also use set operations on languages

• $L_1\circ L_2=\{xy|x\in L_1,y\in L_2\}$
  • …naturally, $L_1\circ L_1=L_1^2$
• $\overline{L_1}={\Sigma }^{\ast }-L_1$

---

A language given a grammar is defined as a set of terminal-only strings that are derivable from the starting strings. More formally:

$$L(G)=\{w\in T^{\ast }|S\stackrel{\ast }{\Rightarrow }w\}$$