Синтаксична діаграма

Синтакси́чна діагра́ма — це орієнтований граф з одним вхідним ребром і одним вихідним ребром і позначеними вершинами. Синтаксична діаграма задає мову. Ланцюжок позначок при вершинах на будь-якому шляху від вхідного ребра до вихідного — це ланцюжок мови, що задається синтаксичною діаграмою. Тому можна вважати, що синтаксична діаграма — це одна з форм породжувальної граматики автоматних мов. Синтаксичні діаграми і скінченні автомати мають тісний зв'язок: будь-яка автоматна мова задається синтаксичною діаграмою і навпаки, за будь-якою синтаксичною діаграмою можна побудувати скінченний автомат (у загальному випадку недетермінований), що розпізнає ту ж мову, яку задає діаграма.

Побудувавши за синтаксичною діаграмою відповідний розпізнавальний скінченний автомат, можна потім реалізувати цей автомат або апаратно, або програмно.

Таким чином, синтаксичні діаграми можуть служити не тільки для породження, а й для розпізнавання автоматних мов.

Див. також

• Синтаксичний аналіз

Джерела

• Hopcroft, John E.; ; Ullman, Jeffrey D. (2001). Вступ до теорії автоматів, мов і обчислень (вид. 2nd). Addison–Wesley. с. 521.(англ.)
• Карпов Ю. Г. Теория автоматов. — СПб.: Питер, 2002. — С. 224.