Алфавит

Алфавит link

В формальной теории языков и теории кодирования алфавитом называется просто конечное, непустое множество символов, из которых строятся строки. Формально:

• Алфавит обозначается заглавной греческой буквой, чаще всего $\Sigma$.
• Каждый элемент $\Sigma$ называется символом или знаком.
• Под «конечным» понимается, что в $\Sigma$ содержится ограниченное число символов (чтобы их можно было перечислить).
• Под «непустым» понимается, что в $\Sigma$ должен быть хотя бы один символ.

Примеры link

• $\Sigma = \lbrace 0,1 \rbrace $ - двоичный алфавит.
• $\Sigma = \lbrace a,b,…,z \rbrace $ - алфавит строчных букв английского языка.
• $\Sigma = \lbrace A,…,Z,a,…,z,0,…,9 \rbrace $ - алфавит буквенно-цифровых символов.

Замыкание Клини link

В формальной теории языков, для алфавита $\Sigma$:

$$ \Sigma^* = \bigcup_{k=0}^{\infty} \Sigma^k $$

это замыкание Клини (или звезда Клини) над $\Sigma$, то есть множество всех конечных строк (включая пустую строку), которые можно составить из символов $\Sigma$. Конкретно:

• $\Sigma^0 = \lbrace \emptyset \rbrace$, где $\emptyset$ — пустая строка.
• $\Sigma^1 = \lbrace \Sigma \rbrace$
• $\Sigma^2 = \lbrace ab \mid a, b \in \Sigma \rbrace$
• И так далее, вплоть до $\Sigma^k$ для любого неотрицательного целого $k$.

Следовательно,

$$ \Sigma^* = \lbrace \emptyset \rbrace \cup \Sigma \cup \Sigma^2 \cup \Sigma^3 \cup … $$

Примеры link

Если $\Sigma = \lbrace 0,1 \rbrace$, то

$$ \Sigma^* = \lbrace \emptyset,0,1,00,01,10,11,000,… \rbrace $$