Presentation of push-down automation as oriented multigraphs
Alexey Belousov, Sergey B. Tkachev · Science and Education of the Bauman MSTU · 2012
 òåîðèè ôîðìàëüíûõ ÿçûêîâ âàæíîå ìåñòî çàíèìàþò êîíòåêñòíî-ñâîáîäíûå ãðàììàòèêè (ÊÑ-ãðàììàòèêè) è êîíòåêñòíî-ñâîáîäíûå ÿçûêè (ÊÑ-ÿçûêè).Ïðîáëåìà ðàñïîçíàâàíèÿ äëÿ ÊÑ-ÿçûêîâ ðåøàåòñÿ ñ ïîìîùüþ àâòîìàòîâ ñ ìàãàçèííîé ïàìÿòüþ (ÌÏ-àâòîìàòîâ).Äëÿ çàäàíèÿ ÌÏ-àâòîìàòîâ èñïîëüçóåòñÿ èõ ôîðìàëüíîå ïðåäñòàâëåíèå, êîòîðîå â îáùåì ñëó÷àå ÿâëÿåòñÿ äîñòàòî÷íî ãðîìîçäêèì.Èçâåñòíî, ÷òî äëÿ ðåãóëÿðíûõ ãðàììàòèê è ðåãóëÿðíûõ ÿçûêîâ ðàñïîçíàþùèìè ìîäåëÿìè ÿâëÿþòñÿ êîíå÷íûå àâòîìàòû, êîòîðûå äîïóñêàþò íàãëÿäíîå ïðåäñòàâëåíèå â âèäå âçâåøåííûõ îðèåíòèðîâàííûõ ãðàôîâ [1].Òàêîå ïðåäñòàâëåíèå ïîçâîëÿåò àíàëèçèðîâàòü ñâîéñòâà êîíå÷íîãî àâòîìàòà è â àíàëèòè÷åñêîì âèäå íàõîäèòü ðåãóëÿðíîå âûðàæåíèå, îïèñûâàþùåå ÿçûê, äîïóñêàåìûé êîíå÷íûì àâòîìàòîì. ñòàòüå ðàññìàòðèâàåòñÿ ïðåäñòàâëåíèå ÌÏ-àâòîìàòà â âèäå îðèåíòèðîâàííîãî ìóëüòèãðàôà, âïåðâûå ââåäåííîå àâòîðàìè â [1].Ýòî ïðåäñòàâëåíèå ÌÏ-àâòîìàòà, ïîìèìî ñâîåé íàãëÿäíîñòè, ïîçâîëÿåò ëåãêî äîêàçûâàòü íåêîòîðûå ïîëåçíûå ñâîéñòâà ÌÏ-àâòîìàòîâ.Îòìåòèì, ÷òî ìóëüòèãðàôû ÌÏ-àâòîìàòîâ ðàññìàòðèâàþòñÿ òàêæå â [3, 4], ãäå îíè íàçûâàþòñÿ äèàãðàììàìè, íî èñïîëüçóþòñÿ èñêëþ÷èòåëüíî êàê èëëþñòðàöèè.