1610906280-c80d8404f2eaa01776b47d41b0f18e85 (824375), страница 4
Текст из файла (страница 4)
. . , sk , rk i, где r0 , . . . , rk ∈ Q,s1 , . . . , sk ∈ A и δ(ri , si+1 ) = ri+1 для всех i < k. Если hr0 , s1 , r1 , . . . , sk , rk i — путь вавтомате, то будем обозначать его черезs1s2skr0 −→r1 −→. . . −→rkи говорить, что слово w = s1 s2 . . . sk читается вдоль дуг данного пути. В частности, пустое слово Λ читается вдоль пути hr0 i, состоящего из одного состояния и несодержащего ни одной дуги.Определение.
Пусть A = hQ, A, δ, q0 , F i — д.к.а. Расширим функцию δ до функцииδ ∗ : Q × A∗ → Q следующим образом индукцией по длине слова:δ ∗ (q, Λ) = q,δ ∗ (q, wa) = δ(δ ∗ (q, w), a),где q ∈ Q, w ∈ A∗ , a ∈ A.Определение. Говорят, что д.к.а. A = hQ, A, δ, q0 , F i распознает слово w ∈ A∗ , еслиδ ∗ (q0 , w) ∈ F .Другими словами, слово w = s1 s2 . . . sk распознается автоматом, если в нем существует путьs1s2skq0 = r0 −→r1 −→. . . −→rk ∈ Fтакой, что он начинается в начальном состоянии q0 , вдоль его дуг читается словоs1 s2 .
. . sk (в детерминированном автомате такой путь определяется однозначно послову w) и заканчивается в некотором выделенном состоянии.Определение. Через T (A) = {w ∈ A∗ | δ ∗ (q0 , w) ∈ F } будем обозначать язык всехслов, распознаваемых конечным автоматом A.Определение. Язык L ⊆ A∗ называется автоматным, если существует конечныйавтомат A такой, что L = T (A).Пример (продолжение). Автомат из предыдущего примера распознает в точностивсе слова в алфавите {0, 1}, которые содержат подслово 11, т. е. T (A) = {w ∈ {0, 1}∗ |w содержит подслово 11}. Действительно, начав чтение произвольного слова w в начальном состоянии данного автомата, попасть в выделенное состояние можно, толькопройдя по дуге, ведущей из q0 в q1 (помеченной 1), а затем сразу же по дуге, ведущейиз q1 в q2 (тоже помеченной 1), — такое возможно лишь в случае, когда w содержитдве единицы подряд.§ 5. Недетерминированные конечные автоматы§ 5.15Недетерминированные конечные автоматыНедетерминированные конечные автоматы отличаютсяот детерминированных тем, что из любого состояния qaпосле считывания символа a возможны сразу несколько- iqq i2(или ни одного) переходов в состояния, принадлежащиеiaмножеству возможных состояний ∆(q, a).
Это означаq3ет, что автомат может продолжить дальнейший процессчтения символов, перейдя в любое из возможных состояний.Можно считать, что в таких ситуациях работа автомата разветвляется на несколько параллельных ветвей вычислений, каждая из которых начинается с определенногосостояния qi ∈ ∆(q, a). Если ∆(q, a) пусто, то работа автомата вдоль данной ветви вычислений заканчивается в состоянии q, даже если на входной ленте осталисьнесчитанные символы.
Таким образом, вдоль одних ветвей вычислений автомат может прочитать все входные символы и остановится в выделенном состоянии, вдольдругих может прочитать все символы, но остановится в невыделенном состоянии,вдоль третьих ветвей работа автомата «обрывается на полуслове».Перейдем к формальным определениям, связанным с недетерминированными автоматами.a- iq1Определение.
Недетерминированным конечным автоматом (сокращенно н.к.а.)называется упорядоченная пятерка A = hQ, A, ∆, q0 , F i, в которой Q, A, q0 , F определяются и называются так же, как в детерминированном случае, а функция переходов∆ является функцией вида ∆ : Q × A → P (Q), где P (Q) — множество всех подмножеств Q (см. аксиому степени из § 1).Графическое изображение недетерминированных автоматовПри графическом изображении недетерминированных автоматов используютсяте же обозначения, что и в детерминированном случае. При этом из одного состояния автомата могут выходить сразу несколько (или нисколько) стрелок, помеченныходной и той же буквой алфавита. Дуга, выходящая из состояния q, входящая в состояние q 0 , помеченная символом a, присутствует в схеме автомата тогда и толькотогда, когда q 0 ∈ ∆(q, a).Пример.
Например, автомат A = hQ, A, ∆, q0 , F i, где A = {0, 1}, Q = {q0 , q1 , q2 },F = {q2 }, а функция переходов задается соотношениями∆(q0 , 0) = {q0 },∆(q0 , 1) = {q0 , q1 },∆(q1 , 0) = ∅,∆(q1 , 1) = {q2 },∆(q2 , 0) = ∅,∆(q2 , 1) = ∅,имеет следующее графическое изображение:0,¨¥1? 1 - iH i©q0q11 - idq2Определение. Путь в недетерминированном конечном автомате A=hQ, A, ∆, q0 , F iопределяется и обозначается так же, как в детерминированном случае, нужно лишьусловие δ(ri , si+1 ) = ri+1 заменить на условие ri+1 ∈ ∆(ri , si+1 ).16Глава II. Конечные автоматы и формальные грамматикиОпределение.
Говорят, что н.к.а. A=hQ, A, ∆, q0 , F i распознает слово s1 s2 . . . sk ∈A∗ , если существует последовательность состояний q0 = r0 , r1 , . . . , rk такая, чтоr1 ∈ ∆(r0 , s1 ),r2 ∈ ∆(r1 , s2 ),......rk ∈ ∆(rk−1 , sk ),и при этом rk ∈ F .Другими словами, слово w = s1 s2 . . . sk распознается автоматом, если в нем существует хотя бы один путьs2sks1. . . −→rk ∈ Fr1 −→q0 = r0 −→такой, что он начинается в начальном состоянии q0 , вдоль его дуг читается словоs1 s2 . . . sk (в недетерминированном автомате такой путь определяется неоднозначнопо слову w) и заканчивается в некотором выделенном состоянии.Определение.
Как и раньше, через T (A) обозначается язык всех слов, распознаваемых автоматом A.Пример (продолжение). Автомат из предыдущего примера распознает в точностивсе слова в алфавите {0, 1}, которые имеют суффикс 11, т. е. T (A) = {w ∈ {0, 1}∗ |∃v ∈ {0, 1}∗ (w = v11)}. Действительно, любой путь, заканчивающийся в выделен11ном состоянии данного автомата, обязан содержать участок q0 −→ q1 −→ q2 . Отсюдаследует, что слова, распознаваемые A, должны содержать хотя бы одно вхождениеподслова 11.
Поскольку из выделенного состояния нет выходящих стрелок, то любойпуть, содержащий описанный выше участок, обрывается как раз после прохожденияданного участка. Отсюда следует, что в словах, распознаваемых автоматом, послекрайнего справа вхождения подслова 11 нет букв.Теорема 3 (о детерминизации).
Для любого недетерминированного конечного автомата A существует детерминированный конечный автомат A такой, что T (A) =T (A).Доказательство. Пусть A = hQ, A, ∆, q0 , F i — исходный н.к.а. Определим следующий д.к.а. A = hQ, A, δ, q 0 , F i (см. пример на рисунке):а) Q = P (Q);Sб) δ(q, a) = ∆(r, a), где q ∈ Q и a ∈ A;r∈qв) q 0 = {q0 };г) F = {q ∈ Q | q ∩ F 6= ∅}.A:a¨¥? a, b - iH id©q0q1a¨¥a - id?A:HH©©H i©{q }Z0{q0 , q1 }ZbZbZZ~?¾¥d a, b - iia, b¦{q1 }∅§ 5.
Недетерминированные конечные автоматы17Докажем, что T (A) = T (A), показав два включения: T (A) ⊆ T (A) и T (A) ⊆ T (A).Пусть слово w = s1 . . . sk ∈ T (A). Следовательно, существуют такие состоянияr0 , r1 , . . . , rk ∈ Q, чтоq0 = r0 ,r1 ∈ ∆(r0 , s1 ),r2 ∈ ∆(r1 , s2 ),......rk ∈ ∆(rk−1 , sk ),rk ∈ F.Иначе говоря, слово w читается вдоль дуг следующего пути в автомате A.H© ir0s1- is2r1- ···sk- idrkПодадим слово w на вход автомата A.
Тогда он будет находиться в следующихсостояниях:r0 = q 0 , r1 = δ(r0 , s1 ), . . . , rk = δ(rk−1 , sk ).Докажем индукцией по i 6 k, что ri ∈ ri .10 . Базис индукции очевиден: r0 = q0 ∈ {q0 } = q 0 = r0 .S∆(r, si+1 ). Тогда получаем20 . Пусть ri ∈ ri . Отсюда следует, что ∆(ri , si+1 ) ⊆r∈riSri+1 ∈ ∆(ri , si+1 ) ⊆∆(r, si+1 ) = δ(ri , si+1 ) = ri+1 . Следовательно, ri+1 ∈ ri+1 .r∈riЧто и требовалось доказать.Итак, для любого i 6 k выполняется ri ∈ ri .
В частности, rk ∈ rk . Посколькуrk ∈ F , то rk ∩ F 6= ∅. Следовательно, rk ∈ F . Отсюда заключаем, что w ∈ T (A), изначит включение T (A) ⊆ T (A) доказано.Пусть теперь слово w = s1 . . . sk ∈ T (A), и пусть при чтении данного слова автомат A находился в состоянияхr0 = q0 ,r1 = δ(r0 , s1 ),...,rk = δ(rk−1 , sk ),причем последнее состояние rk ∈ F .Так как rk ∈ F , то rk ∩ F 6= ∅, и значитнайдется rk ∈ rk ∩ F .SТак как rk ∈ rk = δ(rk−1 , sk ) =∆(r, sk ), то найдется rk−1 ∈ rk−1 такое, чтоr∈rk−1rk ∈ ∆(rk−1 , sk ).Так как rk−1 ∈ rk−1 , то аналогично находим rk−2 ∈ rk−2 такое, что выполняетсяrk−1 ∈ ∆(rk−2 , sk−1 ).И так далее.В итоге получаем последовательность r0 , r1 , . .
. , rk ∈ Q такую, что для каждогоi ∈ {1, . . . , k} выполняется ri−1 ∈ ri−1 и ri ∈ ∆(ri−1 , si ). Поскольку r0 ∈ r0 = q 0 = {q0 },заключаем r0 = q0 . Кроме этого, по построению rk ∈ F . Отсюда по определениюследует, что w ∈ T (A). Таким образом, включение T (A) ⊆ T (A) тоже доказано.18Глава II. Конечные автоматы и формальные грамматикиЗамечание.
В заключение параграфа заметим, что в некоторых источниках (см.,например, [4],[12]) используется другое определение недетерминированного конечного автомата, которое отличается от введенного выше тем, что функция переходов ∆имеет вид ∆ : Q×(A∪{Λ}) → P (Q). Автоматы данного типа называют автоматамис Λ-переходами, поскольку в них допускаются дуги, помеченные пустым словом Λ.Наличие дуги, помеченной Λ, выходящей из состояние q и входящей в состояние q 0 ,означает, что автомат, находясь в состоянии q, может перейти в состояние q 0 , не считывая символа с ленты.
Пользуясь терминами из программирования, можно сказать,что в такой ситуации автомат осуществляет безусловный переход из q в q 0 .Соответствующим образом изменяется и определение распознаваемости слова.Слово w = s1 s2 . . . sk , где si — буквы алфавита, распознается автоматом с Λ-переходами, если в нем существует хотя бы один путьt1t2tmr0 −→r1 −→. . . −−→ rmтакой, что он начинается в начальном состоянии r0 , заканчивается в некотором выделенном состоянии rm , и вдоль его дуг читается слово t1 t2 . .
. tm = s1 s2 . . . sk , причемm > k, т. е. некоторые из символов t1 , . . . , tm могут быть пустыми.Такое определение удобно использовать при доказательстве некоторых свойств.Однако добавление Λ-переходов в определение недетерминированного автомата нерасширяет класс автоматных языков, т. е. язык распознается некоторым недетерминированным конечным автоматом (согласно нашему определению) тогда и толькотогда, когда он распознается некоторым недетерминированным конечным автоматом с Λ-переходами. Таким образом, можно окончательно утверждать, что три различных подхода — детерминированные автоматы, недетерминированные автоматыи недетерминированные автоматы с Λ-переходами, эквивалентны.§ 6.Свойства автоматных языковВ данном параграфе мы докажем важные теоретико-множественные свойства автоматных языков, а также покажем, что существуют неавтоматные языки.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
