Синтакси́чна діагра́ма — це орієнтований граф з одним вхідним ребром і одним вихідним ребром і позначеними вершинами. Синтаксична діаграма задає мову. Ланцюжок позначок при вершинах на будь-якому шляху від вхідного ребра до вихідного — це ланцюжок мови, що задається синтаксичною діаграмою. Тому можна вважати, що синтаксична діаграма — це одна з форм породжувальної граматики автоматних мов. Синтаксичні діаграми і скінченні автомати мають тісний зв'язок: будь-яка автоматна мова задається синтаксичною діаграмою і навпаки, за будь-якою синтаксичною діаграмою можна побудувати скінченний автомат (у загальному випадку недетермінований), що розпізнає ту ж мову, яку задає діаграма.
Побудувавши за синтаксичною діаграмою відповідний розпізнавальний скінченний автомат, можна потім реалізувати цей автомат або апаратно, або програмно.
Таким чином, синтаксичні діаграми можуть служити не тільки для породження, а й для розпізнавання автоматних мов.
Див. також
Джерела
- Hopcroft, John E.; ; Ullman, Jeffrey D. (2001). (Вступ до теорії автоматів, мов і обчислень) (вид. 2nd). Addison–Wesley. с. 521.(англ.)
- Карпов Ю. Г. Теория автоматов. — СПб.: Питер, 2002. — С. 224.
![]() | Це незавершена стаття з інформатики. Ви можете проєкту, виправивши або дописавши її. |
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет