==Алфавит и Слово==
(<tex>\gamma</tex>, <tex>\delta</tex> могут быть пустыми)
==Язык==
'''Язык''' - множество строчек, каждая из которых принадлежит <tex>\Sigma^*</tex>, где <tex>\Sigma</tex> - некоторый фиксированный алфавит. Если <tex>\Sigma</tex> - алфавит, и <tex>\L \subseteq Sigma^*</tex>, то <tex>L</tex> - это ''язык над'' <tex>\Sigma</tex>, или ''в'' <tex>\Sigma</tex>. Отметим, что язык в <tex>\Sigma</tex> не обязательно должен содержать цепочка, в которые входят все символы <tex>\Sigma</tex>. Поэтому, если известно, что <tex>L</tex> является языком в <tex>\Sigma</tex>, то можно утверждать, что <tex>L</tex> - это язык над любым алфавитом, содержащим <tex>\Sigma</tex>.
'''Операции над языками'''
1)
* <tex>L \cup M</tex> - ''объединение''
* <tex>L \cap M </tex> - ''пересечение''
* <tex>L \setminus M</tex> - ''разность''
2)
''Дополнение языка''
<tex> \setminus L=L \varepsilon^* \setminus L</tex>
3)
''Конкатенация''
<tex>LM=\left\{\alpha\beta|\alpha \in L, \beta \in M\right\}</tex>
Если язык состоит из одного слова<tex>{\alpha}</tex>, то для упрощения записи его можно обозначить, как <tex>\alpha</tex>. Тогда можно определить <tex>L\alpha</tex> и <tex>L\varepsilon</tex>
4)
''Конкатенация с обратным словом''
<tex>Lс^{-1}=\left\{\alpha|\alpha c \subset L\right\}</tex>
5)
''Замыкание Клини''
<tex>L^*=\bigcup_{i=0}^{\infty}L^i</tex>
<tex>L^i=LL^{i-1}</tex>
<tex>L^1=L</tex>
<tex>L^0=\left\{\varepsilon\right\}</tex>
'''Пример''':
<tex>L=\left\{a,ab\right\}</tex>
<tex>L^*=\left\{\varepsilon,a,ab,aa,aab,aba,abab,...\right\}</tex>
