Нормальний алгоритм Маркова — система послідовних застосувань, підстановок, які реалізують певні процедури отримання нових слів із базових, які побудовані на певному алфавіті. У 1956 році вітчизняним математиком А.А. Марковим було запропоновано нове уточнення поняття алгоритму, яке пізніше було названо його ім'ям. У цьому уточненні виділені нами 7 параметрів були визначені таким чином:

• Сукупність початкових даних - слова в алфавіті S;
• Сукупність можливих результатів - слова в алфавіті W;
• Сукупність можливих проміжних результатів - слова в алфавіті
• Р = SWV, де V - алфавіт службових допоміжних символів.

P * - безліч слів над алфавітом Р, і називається правилом підстановки. Сенс цього правила полягає в тому, що оброблюваний слово w є видимим зліва направо і шукається входження в нього слова a. Слово a називається входженням в слово w, якщо існують такі слова b і n над тим же алфавітом, що і a і w, для яких вірно: w = ban. Якщо входження a в w знайдено, то слово a замінюється на слово g. Всі правила постановки упорядковуються. Спочатку шукається входження для першого правила підстановки. Якщо воно знайдено, то відбувається підстановка і преобразуемое слово знову проглядається зліва направо у пошуках входження. Якщо входження для першого правила не знайдено, то шукається входження для другого правила і т.д. Якщо входження знайдено для i-го правила підстановки, то відбувається підстановка, і перегляд правил починається з першого, а слово проглядається спочатку і зліва направо. Вся сукупність правил підстановки називається схемою алгоритму.

Будь який нормальний алгоритм визначається вказанням алфавіту, в якому він діє, та схеми нормального алгоритма. Алфавітом нормального алгоритма може бути довільний скінченний алфавіт A. Формулами підстановок в алфавіті A називаються вирази подібні p → q (проста пістановка) або p →• q (кінцева підстановка), де p та q — деякі слова в алфавіті A, які називаються лівою та правою частинами формули відповідно (вважається, що алфавіт A не містить символів → та →•).

Кожний нормальний алгоритм в алфавіті A має скінченну кількість таких формул підстановок. Їх записуть у вигляді списку. Цей список називається схемою алгоритма.

Застосування нормального алгоритма до слова s полягає в наступному.

• В заданому списку формул підстановок знаходять першу формулу, ліва частина якої входить до слова s. Знаходять перше входження цієї частини в слові s і замість цього входження підставляють праву частину формули. Це дасть нове слово s₁.
• З отриманим словом s₁ повторюють попередній крок.

Цей процес може обірватись сам собою на деякому слові, в яке не входить ліва частина жодної з формул алгоритма. Крім того, постулють, що описаний вище процес зупиняється, коли до чергового слова застосувати одну із кінцевих формул підстановки, тобто, формул видуp →• q. Якщо процес закінчується, то отримане останнє слово є результатом застосування алгоритма до слова s.