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

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

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

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

Див. також

Джерела

  • Карпов Ю. Г. Теория автоматов. — СПб.: Питер, 2002. — С. 224. ISBN 5-318-00537-3
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.