Синтаксична діаграма
Синтакси́чна діагра́ма — це орієнтований граф з одним вхідним ребром і одним вихідним ребром і позначеними вершинами. Синтаксична діаграма задає мову. Ланцюжок позначок при вершинах на будь-якому шляху від вхідного ребра до вихідного — це ланцюжок мови, що задається синтаксичною діаграмою. Тому можна вважати, що синтаксична діаграма — це одна з форм породжувальної граматики автоматних мов. Синтаксичні діаграми і скінченні автомати мають тісний зв'язок: будь-яка автоматна мова задається синтаксичною діаграмою і навпаки, за будь-якою синтаксичною діаграмою можна побудувати скінченний автомат (у загальному випадку недетермінований), що розпізнає ту ж мову, яку задає діаграма.
Побудувавши за синтаксичною діаграмою відповідний розпізнавальний скінченний автомат, можна потім реалізувати цей автомат або апаратно, або програмно.
Таким чином, синтаксичні діаграми можуть служити не тільки для породження, а й для розпізнавання автоматних мов.
Див. також[ред. | ред. код]
Джерела[ред. | ред. код]
- Карпов Ю. Г. Теория автоматов. — СПб.: Питер, 2002. — С. 224. ISBN 5-318-00537-3
|
Це незавершена стаття з інформатики. Ви можете допомогти проєкту, виправивши або дописавши її. |