Перейдем к более богатому классу языков - к контекстно-свободным языкам. Они находят применение в разнообразных программных продуктах, таких как компиляторы, средства форматирования исходного кода, средства статического анализа программ, синтаксические редакторы, системы верстки, программы просмотра форматированного текста, поисковые системы.
Начнем рассмотрение
Из класса всех
В последнем разделе этой лекции приводятся важные конкретные примеры однозначных контекстно-свободных грамматик, моделирующих системы правильно вложенных скобок и польскую (префиксную) запись выражений.
Определение 7.1.1.
Выводам в w1,
на которое заменяется начальный символ на первом шаге вывода,
ставится в соответствие вершина дерева,
и к ней проводится дуга из корня.
Полученные таким образом непосредственные потомки корня
упорядочены согласно порядку их меток в слове w1.
Для тех из полученных вершин,
которые помечены символами из множества N,
делается аналогичное построение, и т. д.
Кроной
(
Пример 7.1.2.
Рассмотрим ababab.
Упражнение 7.1.3. Перечислить все
Упражнение 7.1.4. Существует ли праволинейная грамматика без $$\varepsilon$$ -правил, в которой некоторое слово имеет бесконечно много выводов?
Определение 7.2.1.
Вывод в \lmarrow. Правосторонний
( правый ) вывод
определяется аналогично.
В правосторонних выводах вместо $$\Rightarrow$$
пишут \rmarrow.
Пример 7.2.2. Вывод$$S \Rightarrow SS \Rightarrow Sab \Rightarrow SSab \Rightarrow abSab \Rightarrow ababab$$ из примера 7.1.2 не является левосторонним.
Лемма 7.2.3. Для каждого слова, выводимого в контекстно-свободной грамматике, существует левосторонний вывод.
Лемма 7.2.4. Пусть G - контекстно-свободная грамматика над алфавитом $$\Sigma$$. Пусть $$w \in \Sigma ^*$$. Тогда существует взаимно-однозначное соответствие
между левосторонними выводами слова w
в грамматике G
и деревьями вывода в грамматике G,
кроной которых является w.
Пример 7.2.5. Рассмотрим дерево вывода из примера 7.1.2. Ему соответствует левосторонний вывод$$S \mymathrel{\lmarrow} SS \mymathrel{\lmarrow} SSS \mymathrel{\lmarrow} abSS \mymathrel{\lmarrow} ababS \mymathrel{\lmarrow} ababab .$$
Определение 7.2.6.
Пример 7.2.7.
ababab
имеет два левосторонних вывода:$$S \mymathrel{\lmarrow}
SS \mymathrel{\lmarrow}
SSS \mymathrel{\lmarrow}
abSS \mymathrel{\lmarrow}
ababS \mymathrel{\lmarrow}
ababab$$
и$$S \mymathrel{\lmarrow}
SS \mymathrel{\lmarrow}
abS \mymathrel{\lmarrow}
abSS \mymathrel{\lmarrow}
ababS \mymathrel{\lmarrow}
ababab .$$
Пример 7.2.8.
Пусть $$\Sigma = \{ \trm{p} , \trm{\#} ,
\trm{)} , \trm{(} ,
\trm{\lnot} , \trm{\land} , \trm{\lor} \}$$.
p, p#, p##, ...,
с помощью скобок и операторов $$\trm{\lnot}$$, $$\trm{\land}$$
и $$\trm{\lor}$$.
Эта грамматика является однозначной.
Определение 7.2.9.
Пример 7.2.10. Язык, порождаемый контекстно-свободной грамматикой из примера 7.1.2, не является существенно неоднозначным. Он порождается однозначной грамматикой$$\begin{align*} S \; {\to} \; TS , \\ S \; {\to} \; T , \\ T \; {\to} \; ab , \\ T \; {\to} \; aSb . \end{align*}$$
Пример 7.2.11.
Пусть $$\Sigma = \{ a , b , c \}$$.
{akbmcn | k = m или m = n}
является существенно неоднозначным.
Доказательство этого факта можно найти
в [АхоУль, с. 234-236].
Упражнение 7.2.12. Однозначна ли
Упражнение 7.2.13. Однозначна ли
Упражнение 7.2.14. Однозначна ли
Упражнение 7.2.15. Однозначна ли
Упражнение 7.2.16.Найти однозначную
Упражнение 7.2.17.Найти однозначную
Теорема 7.3.1. Каждый праволинейный язык порождается некоторой однозначной праволинейной грамматикой. Другими словами, ни один праволинейный язык не является существенно неоднозначным.
Доказательство. Согласно теоремам 2.4.3 и 2.7.1 исходный язык распознается некоторым детерминированным конечным автоматом. Применив к нему конструкцию из доказательства теоремы 2.4.1, получим однозначную праволинейную грамматику.
Замечание 7.3.2. Этот факт можно получить также из более общей теоремы 12.2.6 с учетом теоремы 12.2.1.
Упражнение 7.3.3. Найти однозначную праволинейную грамматику,
порождающую язык a*((a+b)(a+b))*b*.
Упражнение 7.3.4. Найти однозначную праволинейную грамматику, эквивалентную грамматике$$\begin{align*} S \; {\to} \; T aaa T , \\ S \; {\to} \; T bbb T , \\ T \; {\to} \; a T , \\ T \; {\to} \; b T , \\ T \; {\to} \; \varepsilon . \end{align*}$$
Упражнение 7.3.5. Найти однозначную праволинейную грамматику, эквивалентную грамматике$$\begin{align*} S \; {\to} \; a S , T \; {\to} \; ab Z , \\ S \; {\to} \; b S , T \; {\to} \; bb Z , \\ S \; {\to} \; aa T , Z \; {\to} \; a Z , \\ S \; {\to} \; ab T , Z \; {\to} \; b Z , \\ Z \; {\to} \; \varepsilon . \end{align*}$$
Упражнение 7.3.6. Существует ли праволинейная грамматика
в нормальной форме
с n вспомогательными символами,
не эквивалентная ни одной однозначной праволинейной грамматике
с количеством вспомогательных символов 2n - 1?
Определение 7.4.1. Языком Дика
(Dyck language)
над 2n буквами
называется
{a1,b1,a2,b2,...,an,bn},
порождаемый грамматикой$$\begin{align*}
S \; {\to} \; \varepsilon \\
S \; {\to} \; a_1 S b_1 S \\
\vdots \\
S \; {\to} \; a_n S b_n S .
\end{align*}$$
Замечание 7.4.2.
Словами этого языка являются последовательности
правильно вложенных скобок n типов (если считать символ ai левой скобкой,
а символ bi соответствующей правой скобкой).
Теорема 7.4.3. Слово w над алфавитом {a,b} выводится в грамматике$$\begin{align*}
S \; {\to} \; \varepsilon , \\
S \; {\to} \; a S b S
\end{align*}$$
тогда и только тогда, когда$$| w |_{a} = | w |_{b}$$
и для всех слов $$x \prefix w$$ выполняется неравенство$$| x |_{a} \geq | x |_{b} .$$
Теорема 7.4.4. При любом положительном целом n грамматика из определения 7.4.1 является однозначной.
Определение 7.4.5. Языком Лукасевича
(Lukasiewicz language)
над n + 1 буквами
называется
{a0,a1,...,an},
порождаемый грамматикой$$\begin{align*}
S \; {\to} \; a_0 , \\
S \; {\to} \; a_1 S , \\
S \; {\to} \; a_2 S S , \\
\vdots \\
S \; {\to} \; a_n S^n .
\end{align*}$$
Теорема 7.4.6. Слово w над алфавитом {a0,a1,...,an} принадлежит языку Лукасевича
над n + 1 буквами
тогда и только тогда, когда$$\sum_{i=0}^n (i-1) | w |_{a_i} = -1$$
и для всех слов $$x \prefix w$$, кроме x = w, выполняется неравенство$$\sum_{i=0}^n (i-1) | x |_{a_i} \geq 0 .$$
Теорема 7.4.7. При любом $$n \in \mathbb{N}$$ грамматика из определения 7.4.5 является однозначной.
Упражнение 7.4.8. Принадлежит ли слово aababb
языку, порождаемому грамматикой$$\begin{align*}
S \; {\to} \; a S b S , \\
S \; {\to} \; \varepsilon ?
\end{align*}$$
Упражнение 7.4.9. Принадлежит ли слово cacbcbbacacccaaaacabcaa
языку, порождаемому грамматикой$$\begin{align*}
S \; {\to} \; a , \\
S \; {\to} \; b S , \\
S \; {\to} \; c S S ?
\end{align*}$$
Упражнение 7.4.10. Эквивалентны ли грамматика$$\begin{align*} T \; {\to} \; a , \\ T \; {\to} \; T T , \\ T \; {\to} \; T T b ? \end{align*}$$ и грамматика$$\begin{align*} R \; {\to} \; a , \\ R \; {\to} \; R a , \\ R \; {\to} \; R R b ? \end{align*}$$
Упражнение 7.4.11. Описать язык, порождаемый грамматикой$$\begin{align*} F \; {\to} \; a b , \\ F \; {\to} \; a F b, \\ F \; {\to} \; F F . \end{align*}$$
Упражнение 7.4.12. Описать язык, порождаемый грамматикой$$\begin{align*} F \; {\to} \; a , \\ F \; {\to} \; b F, \\ F \; {\to} \; c F F, \\ F \; {\to} \; d F F F . \end{align*}$$
Упражнение 7.4.13. Найти однозначную
Перейдем к более богатому классу языков - к контекстно-свободным языкам. Они находят применение в разнообразных программных продуктах, таких как компиляторы, средства форматирования исходного кода, средства статического анализа программ, синтаксические редакторы, системы верстки, программы просмотра форматированного текста, поисковые системы.
Начнем рассмотрение
Из класса всех
В последнем разделе этой лекции приводятся важные конкретные примеры однозначных контекстно-свободных грамматик, моделирующих системы правильно вложенных скобок и польскую (префиксную) запись выражений.
Определение 7.1.1.
Выводам в w1,
на которое заменяется начальный символ на первом шаге вывода,
ставится в соответствие вершина дерева,
и к ней проводится дуга из корня.
Полученные таким образом непосредственные потомки корня
упорядочены согласно порядку их меток в слове w1.
Для тех из полученных вершин,
которые помечены символами из множества N,
делается аналогичное построение, и т. д.
Кроной
(
Пример 7.1.2.
Рассмотрим ababab.
Упражнение 7.1.3. Перечислить все
Упражнение 7.1.4. Существует ли праволинейная грамматика без $$\varepsilon$$ -правил, в которой некоторое слово имеет бесконечно много выводов?
Определение 7.2.1.
Вывод в \lmarrow. Правосторонний
( правый ) вывод
определяется аналогично.
В правосторонних выводах вместо $$\Rightarrow$$
пишут \rmarrow.
Пример 7.2.2. Вывод$$S \Rightarrow SS \Rightarrow Sab \Rightarrow SSab \Rightarrow abSab \Rightarrow ababab$$ из примера 7.1.2 не является левосторонним.
Лемма 7.2.3. Для каждого слова, выводимого в контекстно-свободной грамматике, существует левосторонний вывод.
Лемма 7.2.4. Пусть G - контекстно-свободная грамматика над алфавитом $$\Sigma$$. Пусть $$w \in \Sigma ^*$$. Тогда существует взаимно-однозначное соответствие
между левосторонними выводами слова w
в грамматике G
и деревьями вывода в грамматике G,
кроной которых является w.
Пример 7.2.5. Рассмотрим дерево вывода из примера 7.1.2. Ему соответствует левосторонний вывод$$S \mymathrel{\lmarrow} SS \mymathrel{\lmarrow} SSS \mymathrel{\lmarrow} abSS \mymathrel{\lmarrow} ababS \mymathrel{\lmarrow} ababab .$$
Определение 7.2.6.
Пример 7.2.7.
ababab
имеет два левосторонних вывода:$$S \mymathrel{\lmarrow}
SS \mymathrel{\lmarrow}
SSS \mymathrel{\lmarrow}
abSS \mymathrel{\lmarrow}
ababS \mymathrel{\lmarrow}
ababab$$
и$$S \mymathrel{\lmarrow}
SS \mymathrel{\lmarrow}
abS \mymathrel{\lmarrow}
abSS \mymathrel{\lmarrow}
ababS \mymathrel{\lmarrow}
ababab .$$
Пример 7.2.8.
Пусть $$\Sigma = \{ \trm{p} , \trm{\#} ,
\trm{)} , \trm{(} ,
\trm{\lnot} , \trm{\land} , \trm{\lor} \}$$.
p, p#, p##, ...,
с помощью скобок и операторов $$\trm{\lnot}$$, $$\trm{\land}$$
и $$\trm{\lor}$$.
Эта грамматика является однозначной.
Определение 7.2.9.
Пример 7.2.10. Язык, порождаемый контекстно-свободной грамматикой из примера 7.1.2, не является существенно неоднозначным. Он порождается однозначной грамматикой$$\begin{align*} S \; {\to} \; TS , \\ S \; {\to} \; T , \\ T \; {\to} \; ab , \\ T \; {\to} \; aSb . \end{align*}$$
Пример 7.2.11.
Пусть $$\Sigma = \{ a , b , c \}$$.
{akbmcn | k = m или m = n}
является существенно неоднозначным.
Доказательство этого факта можно найти
в [АхоУль, с. 234-236].
Упражнение 7.2.12. Однозначна ли
Упражнение 7.2.13. Однозначна ли
Упражнение 7.2.14. Однозначна ли
Упражнение 7.2.15. Однозначна ли
Упражнение 7.2.16.Найти однозначную
Упражнение 7.2.17.Найти однозначную
Теорема 7.3.1. Каждый праволинейный язык порождается некоторой однозначной праволинейной грамматикой. Другими словами, ни один праволинейный язык не является существенно неоднозначным.
Доказательство. Согласно теоремам 2.4.3 и 2.7.1 исходный язык распознается некоторым детерминированным конечным автоматом. Применив к нему конструкцию из доказательства теоремы 2.4.1, получим однозначную праволинейную грамматику.
Замечание 7.3.2. Этот факт можно получить также из более общей теоремы 12.2.6 с учетом теоремы 12.2.1.
Упражнение 7.3.3. Найти однозначную праволинейную грамматику,
порождающую язык a*((a+b)(a+b))*b*.
Упражнение 7.3.4. Найти однозначную праволинейную грамматику, эквивалентную грамматике$$\begin{align*} S \; {\to} \; T aaa T , \\ S \; {\to} \; T bbb T , \\ T \; {\to} \; a T , \\ T \; {\to} \; b T , \\ T \; {\to} \; \varepsilon . \end{align*}$$
Упражнение 7.3.5. Найти однозначную праволинейную грамматику, эквивалентную грамматике$$\begin{align*} S \; {\to} \; a S , T \; {\to} \; ab Z , \\ S \; {\to} \; b S , T \; {\to} \; bb Z , \\ S \; {\to} \; aa T , Z \; {\to} \; a Z , \\ S \; {\to} \; ab T , Z \; {\to} \; b Z , \\ Z \; {\to} \; \varepsilon . \end{align*}$$
Упражнение 7.3.6. Существует ли праволинейная грамматика
в нормальной форме
с n вспомогательными символами,
не эквивалентная ни одной однозначной праволинейной грамматике
с количеством вспомогательных символов 2n - 1?
Определение 7.4.1. Языком Дика
(Dyck language)
над 2n буквами
называется
{a1,b1,a2,b2,...,an,bn},
порождаемый грамматикой$$\begin{align*}
S \; {\to} \; \varepsilon \\
S \; {\to} \; a_1 S b_1 S \\
\vdots \\
S \; {\to} \; a_n S b_n S .
\end{align*}$$
Замечание 7.4.2.
Словами этого языка являются последовательности
правильно вложенных скобок n типов (если считать символ ai левой скобкой,
а символ bi соответствующей правой скобкой).
Теорема 7.4.3. Слово w над алфавитом {a,b} выводится в грамматике$$\begin{align*}
S \; {\to} \; \varepsilon , \\
S \; {\to} \; a S b S
\end{align*}$$
тогда и только тогда, когда$$| w |_{a} = | w |_{b}$$
и для всех слов $$x \prefix w$$ выполняется неравенство$$| x |_{a} \geq | x |_{b} .$$
Теорема 7.4.4. При любом положительном целом n грамматика из определения 7.4.1 является однозначной.
Определение 7.4.5. Языком Лукасевича
(Lukasiewicz language)
над n + 1 буквами
называется
{a0,a1,...,an},
порождаемый грамматикой$$\begin{align*}
S \; {\to} \; a_0 , \\
S \; {\to} \; a_1 S , \\
S \; {\to} \; a_2 S S , \\
\vdots \\
S \; {\to} \; a_n S^n .
\end{align*}$$
Теорема 7.4.6. Слово w над алфавитом {a0,a1,...,an} принадлежит языку Лукасевича
над n + 1 буквами
тогда и только тогда, когда$$\sum_{i=0}^n (i-1) | w |_{a_i} = -1$$
и для всех слов $$x \prefix w$$, кроме x = w, выполняется неравенство$$\sum_{i=0}^n (i-1) | x |_{a_i} \geq 0 .$$
Теорема 7.4.7. При любом $$n \in \mathbb{N}$$ грамматика из определения 7.4.5 является однозначной.
Упражнение 7.4.8. Принадлежит ли слово aababb
языку, порождаемому грамматикой$$\begin{align*}
S \; {\to} \; a S b S , \\
S \; {\to} \; \varepsilon ?
\end{align*}$$
Упражнение 7.4.9. Принадлежит ли слово cacbcbbacacccaaaacabcaa
языку, порождаемому грамматикой$$\begin{align*}
S \; {\to} \; a , \\
S \; {\to} \; b S , \\
S \; {\to} \; c S S ?
\end{align*}$$
Упражнение 7.4.10. Эквивалентны ли грамматика$$\begin{align*} T \; {\to} \; a , \\ T \; {\to} \; T T , \\ T \; {\to} \; T T b ? \end{align*}$$ и грамматика$$\begin{align*} R \; {\to} \; a , \\ R \; {\to} \; R a , \\ R \; {\to} \; R R b ? \end{align*}$$
Упражнение 7.4.11. Описать язык, порождаемый грамматикой$$\begin{align*} F \; {\to} \; a b , \\ F \; {\to} \; a F b, \\ F \; {\to} \; F F . \end{align*}$$
Упражнение 7.4.12. Описать язык, порождаемый грамматикой$$\begin{align*} F \; {\to} \; a , \\ F \; {\to} \; b F, \\ F \; {\to} \; c F F, \\ F \; {\to} \; d F F F . \end{align*}$$
Упражнение 7.4.13. Найти однозначную
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.