Методы трансляции-1 2022
Формальные языки Алфавит — конечное множество символов. А = {0,1} — алфавит из двух символов: 0 и 1. Предложения языка – цепочки символов. Множество всех цепочек над алфавитом А обозначается А*. Определение. Формальный язык L над алфавитом А — это подмножество цепочек из множества всех цепочек алфавита А: L ⊆ А*. Примеры Конечный язык можно задать явно: L = {00, 01, 10, 11}. Бесконечный язык описывается либо словами, либо формально, чтобы определить цепочки, входящие в него. Пример: язык состоит из цепочек над алфавитом {0,1}, начинающихся с единицы, за которой следует чётное число нулей: L0 = {1, 100, 10000, 1000000, …}. Пример: в язык входят цепочки из 0 и 1 с нечётной длиной и количеством нулей не более 5. Пример: язык – последовательность натуральных чисел в десятичной записи, разделённых запятыми.