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

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

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

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