Блоґ одного кібера

Історія хвороби контуженого інформаційним вибухом

Конспекти 2. Спроба експорту.

with 8 comments

Сьогодні я вирішив повторити вчорашній експеримент. Хоча на парі було холодно, пальці мерзли, і набиралось важко. Але все таки, я навіть деколи встигав набирати з майже з тою швидкістю з якою він (Викладач) говорить. (Він давав фору, коли писав по дошці ключові слова). Швидкість формул в мене трохи більша.

Правда це все через те, що я пишу в дивному псевдокоді. Але зате його потім можна легко перетворити в будь-який інший формат.

Правда не зовсім легко, бо мій псевдокод не сильно формальний, і ще багато речей треба робити руками. Але дещо було швидко:
:'<,'>s/!def/<strong>Означення<\/strong>
:'<,'>s/|=/\models
:'<,'>s/.../\ldots

Як приблизно воно має виглядати:


Системне програмування

вівторок, 27 жовтня 2009 10:50:06 +0200

Мінімізація скінченних автоматів (детермінованих)

  1. Існує алгоритм вилучення тупикових станів
  2. вилучення недосяжних станів
  3. Побудови мінімального автомата

Означення
Два стани називаються k-еквівалентними, якщо для ланцюжка
x, |x| \leq k
(q_1,x) \models ^* (q_1,\varepsilon)
(q_2,x) \models ^* (q_{f_2},\varepsilon)
або ні.

Тобто якщо за k-кроків ми попадаємо в заключні конфігурації, або не в заключні (але одночасно).

Алгоритм побудови класів еквівалентних станів для скінченного автомата

0. Спочатку розбиваємо всі стани на два класи Q\setminus F, F

i. На і-тому кроці ми отримаємо систему множин.
і+1. На наступному кроці ми кажемо що стани залишаються еквівалентні, якщо для будь-якого символа вони переходять в стани з одного класу. Інакше вони потрапляють в різні класи еквівалентності.

(n-2) еквівалентність дає можливість побудувати систему станів.

Програмування скінченних автоматів (детермінованих)

Нагадаємо діаграму переходів скінченного автомата для цілочислових констант. //(Знайти малюнок!)

Нехай слово знаходиться у вхідному файлі. Тоді достатньо написати функцію з таким фрагментом коду:
(розписує код для скінченного автомата, який там намальований)

int g=0; int c;
while ((c=getchar())!=eof)
	switch(q)
	{
		case 0: if(c&gt;='1'&amp;&amp;c&lt;='9') { q=3; break; }
						if (c== '\emptyset') {q=1; break; }
						myerror();
		....
		case 3: if(c&gt;='0'&amp;&amp;c&lt;=9) {q=3; break; }
		ну, і так далі.
				
	}
	if(q=='1'||q=='3' ... )  // ok
		else ; //error

Цей стиль програмування має великий плюс – ми читаємо тільки по одному символу, і тільки раз. За допомогою getchar.

Далі, якщо ми навчились програмувати маленькі автомати, для нашої лаболаторної потрібно розробити лексичний аналізатор.

Методика програмування лексичних аналізаторів на основі скінченних автоматів

Коли ми виписуємо класи лексем, то множина всіх лексем – об’єднання цих класів.

Малюнок1.

Таким чином ми можемо зобразити діаграму переходів ДСкА який розпізнає лексеми мови C. ПРограма такого автомата виливається в 200-300 рядків тексту. За дві години програмується, якщо на побудову автомата було потрачено годину.

Провівши розмову про програмууання скінченних автоматів переходимо до того, як автоматизувати процес програмування лексичного аналізатора. Через метасистеми. Але для цього треба трохи теорії.

Скінченні автомати та праволінійні граматики

Означення
G= називається праволінійною, якщо P: A_i \to \omega A_j A_i, A_j \in N
A_i \to \omega\ \ \omega \in \Sigma^*

Для довільної праволінійної граматики G можна побудувати автомат M, такий що L(M)=L(G).
Твердження конструктивне, тому пробуємо довести:

A_i \to \omega A_i

\omega = a_1, a_2, \ldots a_p

A_i \to a_1,\underbrace{a_2,\ldots,a_p,A_j}_{B_1}
A_i \to a_1B_1
B_1 \to a_2 B_2
\ldots
B_{p-1} \to a_pA_j

де B_1,\ldots, B_n – нові нетермінали.

A_i \to a_1,a_2, ... a_p
A_2 \to a_1B_1
B_p \to \varepsilon

Тепер, спробуємо побудувати скінченний автомат. Як імена станів скінченного автомата M візмемо нетермінали перетвореної граматики. Тобто якщо взяти діаграму переходів, то всі вершини – нетермінали.

\sigma: A_i \to aB_j То на діаграмі переходів це буде A_j \xrightarrow{a} B_j B_j \in (A_j,a)

A_j \to \varepsilon => A_i \in F

S-аксіома – ім’я початкового стану на діаграмі.

Тепер треба показати, що за n кроків безпосереднього виведення ланцюжка, ми відпрацюєм нашим автоматом. Є ланцюжок \omega \in L(G) тепер спробуємо з конфігурації (q_0, \omega) \models * (q_1,\varepsilon)

вівторок, 27 жовтня 2009 11:20:49 +0200 перерва вівторок, 27 жовтня 2009 11:26:46 +0200

(q_0, a \omega) \models  (A_j,\omega) =>

S => a A_j => \ldots => \omega

А якщо \omega виводиться, то існує скінченна послідовність кроків, яка приведе в заключний стан.

для довільного СкА M можна побудувати праволінійну граматику G, таку що, L(M) = L(G), і навпаки.

Тобто ми показали, що механізм на синтез за потужністю еквівалентний механізму на аналіз.

Зображення скінченних автоматів та граматик страждає тим, що ми повинні виписувати формальні множини, що таке множина станів, конкретизувати поняття. Можна спробувати ці множини позначати якимись виразами. В ТП, ці вирази називаються регулярними.

Регулярні множини та вирази

Означення
Рeгулярна множина – це \emptyset , {\varepsilon}, {a}, // це я вже записав на CybWiki. Як виявилось після леції, регулярні множини, і регулярні мови це одне і те ж.

Регулярні вирази позначають регулярні множини. Таким чином що порожня множина позначається нулем. // теж CybWiki Ура Карнаух!

Вирази зустрічаются в алгебрах, тому ведем мову про Алгебру регулярних виразів. Сигнатура – \{+,\cdot,^*\}.

Тотожності в алгебрі регулярних виразів

За тотожностями можна оптимізувати регулярні вирази.

  1. P+0=0+p=p
  2. p+p=p
  3. p+q=q+p
  4. (r+q)p=rp+qp
  5. p*+p=p*
  6. 0*=\varepsilon

Рівняння в алгебрі регулярних виразів

Називається рівняння виду: X=aX+b, де a,b – РВ. Воно може мати нескінченну кількість розв’язків, або 1, який не залежить від виду a,b. Той що не залежить від виду називаєься мінімальним. Його вид: X=a*b. Перевіримо що це розв’язок підставивши в рівняння:

a^*b = (aa^*b+b) = (aa^*+ \varepsilon ) b = (\varepsilon +a( \varepsilon +a + a^2 \ldots ))b = a^*b

Системи рівнянь в алгебрі регулярних виразів:
\begin{cases} X_1=a_{11}X_1+a_{12}X_2+....+b_1 \\ X_2=a_{21}X_1+a_{22}X_2+....+b_2 \\ \ldots\end{cases}

Де a_{i,j} , b_i – регулярні вирази. Розв’язується методом Гауса. // Жах! поки не взнаю нащо воно треба, записувати не буду. Крім того я ж знаю метод Гауса.

Існує теорія неруxомої точки та мінімального рішення. //Прогуглити

Давайте візьмемо праволінійну граматику
A_j \to \omega A_j
A_i \to \omega
, і випишемо її в такому вигляді:
S \to a_{11} S | a_{12} A_1 | \ldots A_{1n} A_n-1 | \omega_1
Якщо правила S \to a_{1j} A_i відсутньє, то a_1j=0

Вертикальна риска означає або. Тобто об’єднання мов, або додавання регулярних виразів. Тому ми можемо праволінійну граматику виписати в вигляді системи регулярних рівнянь.

Розв’язок системи рівнянь по змінній S дає нам регулярний вираз, який позначає множину слів які породжуються праволінійною граматикою. // Ну от я знаю нащо воно треба

Залишилось від регулярного виразу дійти до скінченного автомата.

СкА=>Праволійні граматики => Регулярні вирази => СкА

Обчислення (інтерпритація) регулярних виразів. В результаті виходить автомат.
Їх зручно обчислювати коли вони в формі ПОЛІЗ.
Наприклад (a+b*)c
a b * + c \cdot
НУ, і як завжди через стек: // я пам’ятаю

В стеку знаходяться автомати. // гг. Треба ще вивчити як робляться операції на автоматах.

вівторок, 27 жовтня 2009 12:09:52 +0200


Вихідний код:

(підсвітка C++, поки не написав свою)

Системне програмування
вівторок, 27 жовтня 2009 10:50:06 +0200

= Мінімізація скінченних автоматів (детермінованих) =

#Існує алгоритм вилучення тупикових станів
#вилучення недосяжних станів
#Побудови мінімального автомата

!def
Два стани називаються k-еквівалентними, якщо для ланцюжка
x, |x| \leq k
(q_1,x) |=* (q_1,\epsilon)
(q_2,x) |=* (q_{f_2},\epsilon)
або ні.

Тобто якщо за k-кроків ми попадаємо в заключні конфігурації, або не в заключні (але одночасно).

== Алгоритм побудови класів еквівалентних станів для скінченного автомата ==
0. Спочатку розбиваємо всі стани на два класи Q\setminus F, F

i. На і-тому кроці ми отримаємо систему множин
і+1. На наступному кроці ми кажемо що стани залишаються еквівалентні, якщо для будь-якого символа вони переходять в стани з одного класу. Інакше вони потрапляють в різні класи еквівалентності.

(n-2) еквівалентність дає можливість побудувати систему станів.

== Програмування скінченних автоматів (детермінованих) ==
Нагадаємо діаграму переходів скінченного автомата для цілочислових констант. //(Знайти малюнок!)

Нехай слово знаходиться у вхідному файлі. Тоді достатньо написати функцію з таким фрагментом коду:

(розписує код для скінченного автомата, який там намальований)

int g=0; int c;
while ((c=getchar())!=eof)
    switch(q)
    {
        case 0: if(c>=‘1’&&c<=‘9’) { q=3; break; }
                        if (c== ‘\emptyset’) {q=1; break; }
                        myerror();
        ….
        case 3: if(c>=‘0’&&c<=9) {q=3; break; }
        ну, і так далі.
                
    }
    if(q==‘1’||q==‘3’ … )  // ok
        else ; //error

Цей стиль програмування має великий + – ми читаємо тільки по одному символу, і тільки раз. getchar.

Далі, якщо ми навчились програмувати маленькі автомати, для нашої лаболаторної потрібно розробити лексичний аналізатор.

== Методика програмування лексичних аналізаторів на основі скінченних автоматів ==
Коли ми виписуємо класи лексем, то множина всіх лексем – об’єднання цих класів.

Малюнок1.

Таким чином ми можемо зобразити діаграму переходів ДСкА який розпізнає лексеми мови C. ПРограма такого автомата виливається в 200300 рядків тексту. За дві години програмується, якщо на побудову автомата було потрачено годину.

Провівши розмову про програмууання скінченних автоматів переходимо до того, як автоматизувати процес програмування лексичного аналізатора. Через метасистеми. Але для цього треба трохи теорії.

= Скінченні автомати та праволінійні граматики =
!def
G=<N,\Sigma,P,S> називається праволінійною, якщо P: A_i -> \omega A_j A_i, A_j \in N
A_i -> \omega \omega \in \Sigma^*

Для довільної праволінійної граматики G можна побудувати автомат M, такий що L(M)=L(G).
Твердження конструктивне, тому пробуємо довести:

A_i \to \omega A_i

\omega = a_1, a_2, \ldots a_p

$$A_i \to a_1,\underbrace{a_2,\ldots,a_p,A_j}{B_1}
A_i \to a_1B_1
B_1 \to a_2 B_2
\ldots
B_{p-1} \to a_pA_j$$

де B_1,\ldots, B_n – нові нетермінали.

$A_i \to a_1,a_2, … a_p
A_2 \to a_1B_1
B_p \to \epsilon$

Тепер, спробуємо побудувати скінченний автомат. Як імена станів скінченного автомата M візмемо нетермінали перетвореної граматики. Тобто якщо взяти діаграму переходів, то всі вершини – нетермінали.

$\sigma: A_i \to aB_j$ То на діаграмі переходів це буде $ A_j \xrightarrow{a} B_j$
        B_j \in (A_j,a)

A_j \to \epsilon => A_i \in F

S-аксіома – ім’я початкового стану на діаграмі.

Тепер треба показати, що за n кроків безпосереднього виведення ланцюжка, ми відпрацюєм нашим автоматом. Є ланцюжок \omega \in L(G) тепер спробуємо з конфігурації (q_0, \omega) |=* (q_1,\epsilon)

вівторок, 27 жовтня 2009 11:20:49 +0200
перерва
вівторок, 27 жовтня 2009 11:26:46 +0200

(q_0, a \omega) |= (A_j,\omega) =>

S => a A_j => … => \omega

А якщо \omega виводиться, то існує скінченна послідовність кроків, яка приведе в заключний стан.

для довільного СкА M можна побудувати праволінійну граматику G, таку що, L(M) = L(G), і навпаки.

Тобто ми показали, що механізм на синтез за потужністю еквівалентний механізму на аналіз.

Зображення скінченних автоматів та грамати страждає тим, що ми повинні виписувати формальні множини, що таке множина станів, конкретизувати поняття. Можна спробувати ці множини позначати якимись виразами. В ТП, ці вирази називаються регулярними.

= Регулярні множини та вирази =
!def
Рeгулярна множина – це \emptyset , {\epsilon}, {a}, // це я вже записав на CybWiki

Регулярні вирази позначають регулярні множини. Таким чином що порожня множина позначається нулем.  // теж CybWiki Ура Карнаух!

Вирази зустрічаются в алгебрах, тому ведем мову про Алгебру регулярних виразів. Сигнатура – {+,\cdot,*}.

== Тотожності в алгебрі регулярних виразів ==
За тотожностями можна оптимізувати регулярні вирази.

#P+0=0+p=p
#p+p=p
#p+q=q+p
#(r+q)p=rp+qp
#p*+p=p*
#0*=\epsilon

== Рівняння в алгебрі регулярних виразів ==
Називається рівняння виду: X=aX+b, де a,b – РВ. Воно може мати нескінченну кількість розв’язків, або 1, який не залежить від виду a,b. Той що не залежить від виду  називаєься мінімальним. Його вид: X=a*b. Перевіримо що це ррозв’язок підставивши в рівняння:

a*b=(aa*b+b)=(aa*+\epsilon)b=(\epsion+a(\epsilon+a+a^2...))b=a*b

Системи рівнянь в алгебрі регулярних виразів
X_1=a_{11}X_1+a_{12}X_2+….+b_1
X_2=a_{21}X_1+a_{22}X_2+….+b_2
….

Де a_{i,j} , b_i – регулярні вирази. Розв’язується методом Гауса. // Жах! поки не взнаю нащо воно треба, записувати не буду. Крім того я ж знаю метод Гауса.

Існує теорія нерузомої точки та мінімального рішення.  //Ооо, як замерзли пальці. Я вже мимо клавші попадаю

давайте візьмемо праволінйну граматику
A_j \to \omega A_j
A_i \to \omega
, і випишемо її в такому вигляді:
S \t a_11 S | a_12 A_1 | … A_1n A_n-1 | \omega_1
Якщо правила S \to a_1j A_i відсутньє, то a_1j=0

Вертикальна риска означає або. Тобто об’єднання мов, або додавання регулярних виразів. Тому ми можемо праволінійну граматику виписати  в вигляді системи регулярних рівнянь.

Розв’язок системи рівнянь по змінній S дає нам регулярний вираз, який позначає множину слів які породжуються праволінійною граматикою. // Ну от я знаю нащо воно треба

Залишилось від регулярного виразу дійти до скінченного автомата.

СкА=>Праволійні граматики => Регулярні вирази => СкА

Обчислення (інтерпритація) регулярних виразів.  В результаті виходить автомат.
Їх зручно обчислювати коли вони в формі ПОЛІЗ.

Наприклад (a+b*)c
a b * + c \cdot
НУ, і як завжди через стек: // я пам’ятаю

В стеку знаходяться автомати. // гг. Треба ще вивчити як робляться операції на автоматах.

вівторок, 27 жовтня 2009 12:09:52 +0200

Advertisements

Written by bunyk

Жовтень 27, 2009 at 15:59

Відповідей: 8

Subscribe to comments with RSS.

  1. 1. Буник, я розумію та цілком розділяю твою любов до :read !date. Але переглянь хоча б date –help 😉 Наприклад, вівторок, 27 жовтня 2009 11:20:49 +0200 перерва вівторок, 27 жовтня 2009 11:26:46 +0200 було б краще зробити із date +%T.

    2. Дуже сподобалось, викладай конспекти далі. Бажано в окремій категорії.

    3. Пропоную трошечки допрацювати конспект:
    а) в перевірці розв’язку рівняння в регулярних виразах я б додав ще один крок: розкриття aa* за дистрибутивністю. Бо не одразу зрозуміло, що \varepsilon + aa* = a*
    б) теорія неруxомої точки Може теорема?
    в) інтерпритація інтрерпретація
    Фак. Це ж всього лише конспект.

    ulidtko

    Жовтень 28, 2009 at 13:05

  2. 1. Прочитав. Трохи понервувало, потім здогадався, що % пишеться, як ескейп-символ.

    2. О! Поки що єдина людина яка цінить. Взагалі, то я хотів би, викладати це сам знаєш куди, але там післяопрацювання треба більше. До сих пір пам’ятаю слова Алхіміка: “перенабрати конспект це одне. але структурувати його, це абс інше”

    3. Ну конспекти, справді як завжди слабенької якості. Дозволяю тобі користуватись ними будь-як для покращення своїх. Але ти своїми зі мною поділишся? 🙂

    bunyk

    Жовтень 29, 2009 at 16:25

  3. Ну так от. Для того, щоб не викладати нескінченні “трішки поправлені” версії в різних місцях і не створювати таким чином хаос, існують системи для організації сумісної роботи. Наприклад, svn. Хоча, та ж вікі теж підходить, але там є і свої особливості. Можна спробувати попросити створити окремий простір імен «Конспекти».

    ulidtko

    Жовтень 29, 2009 at 18:00

  4. Простір імен? Може досить простої категорії. І можна приступити прямо зараз, не напрягаючи наших адмінів, яких я підозрюю в ліні.

    bunyk

    Жовтень 29, 2009 at 21:10

  5. І, я тут щойно зрозумів, чому я не викладаю конспект зразу на CybWiki. Бо боюсь опозиції 🙂

    Пропозиція перша: в розділі навчання CybWiki не має бути чернеткою студента, що сидів на лекції. Як ”мінімум”, статті мають бути солідними, закінченими сторінками із конспекту. Бажана ж форма: з формальним означенням, його неформальним розумінням, прикладами і поясненнями. –ulidtko 22:59, 11 червня 2009 (UTC)

    bunyk

    Жовтень 29, 2009 at 21:24

    • Ну от саме тому я і пропоную окремий неймспейс, щоб «чернетковість» конспектів була нормою.

      ulidtko

      Жовтень 29, 2009 at 23:05

      • Я на якійсь вікі бачив статтю, яка називалась “Ідеальна стаття”. Там довго розказували про те, якою має бути ідеальна стаття, а в самому кінці написали. Ідеальна стаття не існує. Зате всі статті мають до неї прямувати.

        Чим окрема категорія гірше окремого простору імен?

        bunyk

        Жовтень 29, 2009 at 23:18

        • тим, що насправді категорії більше схожі на теги, а простори імен — на жорсткіші теки. Та і все одно доведеться ж писати в заголовку “щось-там, конспект”. То чому б одразу не формалізувати? В неймспейс конспектів писати власне конспекти; а з них уже потім, при наявності часу та бажання, робити статті.

          ulidtko

          Жовтень 30, 2009 at 00:32


Залишити відповідь

Заповніть поля нижче або авторизуйтесь клікнувши по іконці

Лого WordPress.com

Ви коментуєте, використовуючи свій обліковий запис WordPress.com. Log Out / Змінити )

Twitter picture

Ви коментуєте, використовуючи свій обліковий запис Twitter. Log Out / Змінити )

Facebook photo

Ви коментуєте, використовуючи свій обліковий запис Facebook. Log Out / Змінити )

Google+ photo

Ви коментуєте, використовуючи свій обліковий запис Google+. Log Out / Змінити )

З’єднання з %s

%d блогерам подобається це: