Мовою над алфавітом A називається будь безліч L ланцюжків (рядків), пропозицій або слів в алфавіті A в загальному випадку сформульованих набором відповідних обмежуючих правил, тобто L A . Зокрема, язики над будь-яким алфавітом A .
Граматики з фазовою структурою
Граматикою з фазовою структурою називається набір G = ( N , T , P , S ), де N алфавіт нетермінальних символів (текстових змінних); вони позначаються великими латинськими літерами; T алфавіт термінальних символів (текстових констант), термінальні символи позначаються малими буквами з початку латинського алфавіту; P кінцеве безліч правил (або продукцій ); правило має вигляд ( T N ) * , причому містить хоч один нетермінальний символ; S початковий нетермінальний символ, S N .
Символи об'єднаного алфавіту V = T N (алфавіту знаків) позначаються малими буквами з кінця латинського алфавіту ( u , v , w , ...).
Основним поняттям граматик є поняття виведення і виводимості. Якщо в граматиці є правило, то з ланцюжка
