Основные определения: алфавит, слово, язык, конкатенация, свободный моноид слов; операции над языками — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Свойства)
м (Свойства)
Строка 30: Строка 30:
 
==Свойства==
 
==Свойства==
  
* Ассоциативность <tex>(\alpha\beta)\gamma=\alpha(\beta\gamma)</tex>
+
* <tex>(\alpha\beta)\gamma=\alpha(\beta\gamma)</tex>
* <tex>\exists \varepsilon </tex>  (нейтральный элемент) такой, что <tex>\alpha\varepsilon=\varepsilon\alpha=\alpha</tex>
+
* <tex>\exists \varepsilon : \alpha\varepsilon=\varepsilon\alpha=\alpha</tex>
  
 
Таким образом, мы получаем '''свободный моноид слов'''.
 
Таким образом, мы получаем '''свободный моноид слов'''.

Версия 00:10, 22 октября 2011

Определение:
Алфавит — конечное непустое множество символов. Условимся обозначать алфавит символом [math]\Sigma[/math].

Наиболее часто используются следующие алфавиты:

  1. [math]\Sigma=\{0, 1\}[/math] — бинарный или двоичный алфавит.
  2. [math]\Sigma=\{a, b, ...,z\}[/math] — множество строчных букв английского алфавита.


Определение:
Слово (цепочка) — это конечная последовательность символов некоторого алфавита.


Определение:
Пустая цепочка — цепочка, не содержащая ни одного символа. Эту цепочку, обозначаемую [math] \varepsilon [/math], можно рассматривать как цепочку в любом алфавите.


Определение:
Длина цепочки — число символов в цепочке. Длину некоторой цепочки [math]w[/math] обычно обозначают [math]|w|[/math].

Если [math]\Sigma[/math] — некоторый алфавит, то можно выразить множество всех цепочек определенной длины, состоящих из символов данного алфавита, используя знак степени. Определим [math]\Sigma^k[/math] как множество всех цепочек длины [math]k[/math], состоящих из символов алфавита [math]\Sigma[/math]. Множество всех цепочек над алфавитом [math]\Sigma[/math] принято обозначать [math]\Sigma^*[/math], то есть [math]\Sigma^*=\{\Sigma^0, \Sigma^1, \Sigma^2, ...\}[/math].


Определение:
Пусть [math]x[/math] и [math]y[/math] — цепочки. Тогда [math]xy[/math] обозначает их конкатенацию, т.е. цепочку, в которой последовательно записаны цепочки x и y.


Свойства

  • [math](\alpha\beta)\gamma=\alpha(\beta\gamma)[/math]
  • [math]\exists \varepsilon : \alpha\varepsilon=\varepsilon\alpha=\alpha[/math]

Таким образом, мы получаем свободный моноид слов.


Определение:
Язык — множество цепочек, каждая из которых принадлежит [math]\Sigma^*[/math], где [math]\Sigma[/math] — некоторый фиксированный алфавит.


Если [math]\Sigma[/math] — алфавит и [math]L \subseteq \Sigma^*[/math], то [math]L[/math] — это язык над [math]\Sigma[/math], или в [math]\Sigma[/math]. Отметим, что язык в [math]\Sigma[/math] не обязательно должен содержать цепочки, в которые входят все символы [math]\Sigma[/math]. Поэтому, если известно, что [math]L[/math] является языком в [math]\Sigma[/math], то можно утверждать, что [math]L[/math] — это язык над любым алфавитом, содержащим [math]\Sigma[/math].