Граматики з фразовою структурою.

Формальна породжувальна граматика G – це формальна система, визначена четвіркою об`єктів G=(V, T, S, P), де V – скінченна непорожня множина, яку називають алфавітом. T- її підмножина, елементи множини T називають термінальними символами. S – початковий символ. P – скінченна множина продукцій вигляду ξ -> η, де ξ та η – ланцюжки над алфавітом V.

Множину V\T позначають N, її елементи називають нетермінальними символами.

Формальні породжувальні граматики часто називають граматиками з фразовою структурою, граматиками безпосередніх складових. Термінальні символи часто називають терміналами, а нетермінальні символи – нетерміналами.

Символи термінального алфавіту позначають малими латинськими бувами чи цифрами, символи нетермінального алфавіту – великими латинськими буквами, ланцюжки над алфавітом V – грецькими буквами. Довжину ланцюжка α позначають l(α) або |α |.

41. Типи граматик з фразовою структурою.

Граматики класифікують за типами продукцій:

Граматики типу 2 називають контекстно вільними, бо нетермінал А у лівій частині продукції A-> η може бути замінений ланцюжком η у довільному оточенні щоразу, коли він зустрічається, тобто незалежно від контексту. Мову, яку породжує граматика типу 2, називають контекстно вільною.

Граматику типу 1 називають контекстно залежною. Якщо в множині продукій Р є продукція вигляду γ μ δ -> γ ν δ, |μ |≤ |ν | то μ можна замінити на ν лише в оточення ланцюжків γ …δ тобто у відповідному контексті. Мову, яку породжує граматика типу 1, називають контекстно залежною.

Граматику типу 3 називають регулярною. Нагадаємо, що в ній можуть бути лише продукції A-> aB, A-> a, S-> λ, де A, B – нетермінали, a- термінал. Мову яку породжує граматика типу 3 називають регулярною.

42. Скінченні автомати з виходом. Способи задання, приклади.

Розглядатимемо скінченні автомати як абстрактні моделі найпростіших пристроїв опрацювання даних. Спосіб викладення орієнтований на теорію формальних мов.

Скінченним автоматом називають систему M=(S, I, O, f, g, s₀), у якій S, I, O – скінченні множини, а f: SxI S, та g: SxI O – функції, визначені на декартовому добутку SxI. Множину S називають множиною станів, f – функцією переходів, g – функцією виходів, виділений елемент s₀єS – початковим станом.

Елементи вхідного алфавіту називають вхідними символами (входами), а вихідного – вихідними символами (виходами).

Рівність f(s_i, x)= s_j, означає, що у разі входу х автомат, який перебуває у стані s_i, а рівність g(s_i, x)=y, - що в цьому разі на виході з’являється у; тут s_i, s_j є f, xєI, yєO.

Оскільки функції f, g визначені на скінченних множинах, то їх можна задавати таблицями. Звичайно дві таблиці зводять в одну і називають таблицею станів, або автоматною таблицею. Ця таблиця містить значення функції переходів f та функції виходів g для всіх пар (s, x), де sєS, xєI.

Ще один поширений і наочний спосіб задання автомата – орієнтований мультиграф, який називають діаграмою станів. Вершини графа відповідають станам; якщо f(s_i, x_i) = s_k та g(s_i, x_i)= y_r, то із вершини s_i у вершину s_k веде дуга, на які записано через кому s_k, y_r. Тут x_jєI, y_rєO. Кратні дуги не обов’язкові; якщо є 2 кратні дуги, то їх можна замінити однією, на якій написати обидві пари вхідний символ – вихідний символ.

43. Скінченні автомати без виходу. Способі задання приклади.

Одне з найважливіших застосувань скінченних автоматів є подання мов. Скінченним автоматом без виходу називають систему станів M=(S, I, f, s₀, F), у якій S – скінченна множина станів, I – скінченний вхідний алфавіт, f: SxI S – функція переходів, визначена на декартовому добутку SxI, s₀єS – початковий стан, F підмножина S – множина заключних (або сприймальних) станів.

Елементи вхідного алфавіту, як і раніше, називають вхідними символами або входами.

Скінченні автомати можна задавати таблицями станів або діаграмами станів. Заклучні стани на діаграмі зобрачають подвійними кружечками. Зазначимо, що в автоматах без виходу є тільки входи (символи вхідного алфавіту І), тому на дугах діаграми записують тільки їх.

Кажуть, що ланцюжок α = x₁ х₂… x_n допускається (сприймається, розпізнається) скінченним автоматом M=(S, I, O, f, s₀, F), якщо він переводить початковий стан s₀ у заключний стан – це означає, що стан f(s₀, α) є елементом множини F. Мова, що допускається (сприймається, розпізнається) автоматом М, позначається L(M), - це множина всіх ланцюжків, які допускаються автоматом М. Два автомати називають еквівалентними, якщо вони допускають одну й ту саму мову.

Недетермінованим скінченним автоматом без виходу називають систему M=(S, I, f, s₀, F), у якій S – скінченна множина станів, І – скінченний вхідний алфавіт, f – функція переходів, яка кожній парі стан-вхід ставить у відповідність множину станів, s₀єS – початковий стан, F підмножина S – множина заключних станів.

44. Машина Тьюрінга.

Машина Тьюрінга – це математична модель пристрою, який породжує обчислювальні процеси. Використовується для теоретичного уточнення поняття алгоритму та його дослідження. У кожній машині Тьюрінга є три частини: 1) стрічка, поділена на комірки, 2) пристрій керування (ПК), 3) голова читання (записування) (Г). З кожною машиною Тьюрінга пов’язані 2 скінченні алфавіти: алфавіт зовнішніх символів А, алфавіт внутрішніх станів Q={ q₀, q₁, …, q_k}. Алфавіт зовнішніх символів А часто називають зовнішнім алфавітом, а його елементи – буквами. Один символ з А називають порожнім, зазвичай його позначають ᴧ. Всі інші букви з А, крім ᴧ, називають не порожніми. Комірку стрічки, в якій записано букву ᴧ, називають порожньою.

Машина Тьюрінга працює в часі, що вважають дискретним, і його моменти занумеровують 1, 2, 3, ….У кожний момент часу стрічка містить скінченну к-сть комірок. Головка пересувається поздовж стрічки; у кожний момент часу головка перебуває над певною коміркою стрічки. У такому разі кажуть, що головка зчитує _букву, яка записана в цій комірці. У наступний момент часу головка залишається над цією ж коміркою (що позначають Н), або пересувається на одну комірку вправо (що позначають П), або пересувається на одну комірку вліво (що позначають Л). Якщо у певний момент t головка перебуває над крайньою коміркою і зсувається на відсутню комірку, то автоматично прибудовується нова порожня (тобто з порожньою буквою ᴧ) комірка, над якою у момент часу t+1 перебуватиме головка. Отже, стрічка є потенціально нескінченною в обидва боки, тобто до неї як зліва, так і справа можуть бути додані нові комірки.

Алфавіт внутрішніх станів Q={ q₀, q₁, …, q_k} – це внутрішня пам’ять. Внутрішня пам’ять скінченна. Елемент q₀ називають заключним внутрішнім станом, а елемент q₁ – початковим внутрішнім станом. Пересування головки поздовж стрічки залежить від букви, яка зчитується і від внутрішнього стану машини. Пристрій керування в кожний момент часу t, залежно від букви, яка зчитується у цей момент на стрічці, і внутрішнього стану машини, виконує такі дії: 1) змінює букву а_і, яка зчитується в момент t на стрічці на нову букву a_j (зокрема, може бути a_j= a_i), 2) пересуває головку в одному із напрямків Н, П, Л, 3) змінює наявний у момент t внутрішній стан машини q_і на новий стан q_j, у якому машина буде в момент часу t+1 (зокрема, може бути q_j= q_i).

Таку дію пристрою керування називають командою, і її записують так: q_i a_i a_jD q_j, де q_і – внутрішній стан машини в даний момент; а_і – буква на стрічці, яка зчитується в цей момент; a_j – буква, на яку змінюється буква а_і; символ D є або Н, або П, або Л і вказує пересування головки; q_j – внутрішній стан машини у наступний момент часу. Виконання однієї команди називають кроком. Робота машини Тьюрінга повністю визначена завданням у перший момент: 1) слова на стрічці, тобто послідовності букв, записаних у комірках стрічки; 2) положення головки Г; 3) внутрішнього стану машини. Сукупність цих трьох умов (у даний момент часу t) називають конфігурацією (у даний момент часу t).