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

Материал из Викиконспекты
Перейти к: навигация, поиск
м
Строка 1: Строка 1:
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
'''Алфавит''' {{---}} конечное непустое множество символов. Условимся обозначать алфавит символом <tex>\Sigma</tex>.
+
'''Алфавит''' {{---}} конечное непустое множество. Условимся обозначать алфавит символом <tex>\Sigma</tex>.
 
}}  
 
}}  
  
Строка 32: Строка 32:
 
<tex>\Sigma^* = \bigcup \limits _{k=0}^\infty \Sigma^k</tex> — множество всех цепочек над алфавитом <tex>\Sigma</tex>.
 
<tex>\Sigma^* = \bigcup \limits _{k=0}^\infty \Sigma^k</tex> — множество всех цепочек над алфавитом <tex>\Sigma</tex>.
 
}}
 
}}
 +
 +
{{Определение
 +
|id = deflanguage
 +
|definition =
 +
'''Язык''' над алфавитом <tex>\Sigma</tex> {{---}} некоторое подмножество <tex>\Sigma^*</tex>. Иногда такие язык называют '''формальными''', чтобы подчеркнуть отличие от языков в привычном смысле.
 +
}}
 +
 +
Отметим, что язык в <tex>\Sigma</tex> не обязательно должен содержать цепочки, в которые входят все символы <tex>\Sigma</tex>. Поэтому, если известно, что <tex>L</tex> является языком над <tex>\Sigma</tex>, то можно утверждать, что <tex>L</tex> {{---}} это язык над любым алфавитом, являющимся надмножеством <tex>\Sigma</tex>.
  
 
{{Определение
 
{{Определение
Строка 44: Строка 52:
  
 
Таким образом, мы получаем '''свободный [[Моноид|моноид]] слов'''.
 
Таким образом, мы получаем '''свободный [[Моноид|моноид]] слов'''.
 
{{Определение
 
|id = deflanguage
 
|definition =
 
'''Язык''' {{---}} множество цепочек, каждая из которых принадлежит <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>.
 

Версия 19:54, 27 октября 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^k[/math] — множество цепочек длины [math]k[/math] над алфавитом [math]\Sigma[/math].


Определение:
[math]\Sigma^* = \bigcup \limits _{k=0}^\infty \Sigma^k[/math] — множество всех цепочек над алфавитом [math]\Sigma[/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].


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


Свойства

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

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