Изменения

Перейти к: навигация, поиск

Автоматы с eps-переходами. Eps-замыкание

681 байт добавлено, 22:15, 6 октября 2010
Нет описания правки
{{В разработке}}
[[Категория: Теория формальных языков]]
==Автоматы с eps-переходами==
Конечный автомат с <tex>\varepsilon</tex>-переходами --- конечный автомат, в котором есть возможность совершать переходы по <tex>\varepsilon</tex>. Формально, <tex>\varepsilon</tex>-НКА <tex>A</tex> можно представить в виде <tex>A={\langle\Sigma,Q,s,T,\delta\rangle}</tex>, где все компоненты имеют тот же смысл, что и для [[Недетерминированные конечные автоматы|НКА]], за исключением <tex>\delta : Q\times \Sigma\bigcup\{\varepsilon\} \to \rho(Q)</tex>.
==Эквивалентность автоматов с переходами по строкам и НКА. Eps-замыкание.==
Рассмотрим автомат, в котором переходы осуществляются по строкам. Это переходы вида <tex><p,\alpha\beta>\vdash<q,\beta></tex>, где <tex>\alpha,\beta</tex> --- строки.
57
правок

Навигация