ТПТ_Лекція_3_Формальні_мови_та_грамматики
Визначення формальних мов і граматик Математичні моделі, що використовують подання текстів у вигляді послідовності символів, називають формальними мовами і граматиками. Кінцева множина символів, неподільних у даному розгляді, називається словником чи алфавітом, а символи, що входять у множину, –буквами алфавіту. Наприклад, алфавіт A = {2, b, c, +, !} містить 5 букв, а алфавіт B = {00, 01, 10, 11} містить 4 букви, кожна з яких складається з двох символів. Послідовність букв алфавіту називається словом чи ланцюжком у цьому алфавіті. Число букв, що входять у слово, називається його довжиною. Наприклад, слово в алфавіті A а= 2bc має довжину l(a) = 3, а слово в алфавіті B b = 0000110010 має довжину l (b) = 5. Теорія побудови трансляторів Визначення формальних мов і граматик Формальною граматикою Г, що породжує множину символів, називається наступна сукупність чотирьох об'єктів: Г = { Vт, VA, I ∈ VA, R }, де VТ – термінальний алфавіт (словник); букви цього алфавіту називаються термінальними символами; з них будуються ланцюжки породжувані граматикою; VА – нетермінальний, допоміжний алфавіт (словник); букви цього алфавіту використовуються при побудові ланцюжків; вони можуть входити в проміжні ланцюжки, але не повинні входити в результат породження; I - початковий символ граматики I ∈ Vа; R - множина правил чи виводу правил вигляду, що α→ β , де α і β - ланцюжки, побудовані з букв алфавіту Vт∪ VА, що називають повним алфавітом (словником) граматики Г. До множини правил граматики можуть також входити правила з порожньою правою частиною вигляду Е → $. Теорія побудови трансляторів