Искусственный интеллект

Каждому правилу Nt^> а сопоставим дугу (переход) из состояния Ь. в состояние bf по входному состоянию а. Пример. Дана автоматная грамматика G: А - {о„ av аъ), N = {TV,, Л^2, N,}, S = TV,, P = {Nt -> axNv N2^> atNv W3-> av 7V,-> atNv W2-> a2}. Порождаемый язык L(G) - {аЛ} v {ax*av n > I). 5* 131 5. Среды и языки Конечный автомат, распознающий язык L(G) (рис. 5.18): А = Ц, аг, о3), В = {6,, fe2, bv Ь4), /: До,, 6.) = {Ь2, Ь3), /(с,, *2) = {*,), А** Ь2) Ьо = bv F = {bj. Этот простой конечный автомат не является детерминированным. Можно показать, что любой недетерминированный конечный автомат может быть преобразован в эквивалентный детерминированный автомат или в систему эквивалентных детерминированных автоматов. Под эквивалентностью автоматов в данном случае понимается их способность распознавать одни и те же языки. Системы автоматов способны распознавать и более мощные языки, например, порождаемые, контекстно-свободными грамматиками. Таким образом, модель конечного автомата может служить основой для распознавания достаточно широкого класса языков. Учитывая это, модель конечного автомата может быть использована для создания агентов, способных выполнять следующие функции.