Свойства регулярных языков (1134638), страница 11
Текст из файла (страница 11)
Два состояния некоторого ДКА различимы,если существует входная цепочка, которая переводит в допускающее только одноиз этих состояний. Если начать с того, что все пары, состоящие из допускающегои недопускающего состояний, различимы, и найти дополнительные пары, которыепо одному символу переходят в различимые состояния, можно обнаружить всепары различимых состояний.♦ Минимизация детерминированных конечных автоматов. Состояния любого ДКАможно разбить на группы взаимно неразличимых состояний. Состояния из двухразных групп всегда различимы. Если заменить каждую группу одним состоянием, получим эквивалентный ДКА с наименьшим числом состояний.ËèòåðàòóðàЗа исключением очевидных свойств замкнутости регулярных выражений (относительнообъединения, конкатенации и итерации), которые были доказаны Клини [6], почти все результаты свойств замкнутости воспроизводят аналогичные результаты, полученные дляконтекстно-свободных языков (этому классу языков посвящены следующие главы). Такимобразом, лемма о накачке для регулярных языков является упрощением соответствующегорезультата для контекстно-свободных языков (Бар-Хиллел, Перлес и Шамир [1]).
Из результатов этой работы следуют некоторые другие свойства замкнутости, представленные вданной главе, а замкнутость относительно обратного гомоморфизма обоснована в [2].ÐÅÇÞÌÅ183Операция деления (см. упражнение 4.2.2) представлена в [3]. В этой работе обсуждаетсяболее общая операция, в которой вместо одиночных символов находятся регулярные языки.Ряд операций “частичного удаления”, начиная с упражнения 4.2.8, в котором говорилось опервых половинах цепочек регулярного языка, был определен в [8].
Сейферас и Мак-Нотон[9] изучили общий случай, когда операция удаления сохраняет регулярность языков.Алгоритмы разрешения, такие как проверка пустоты и конечности регулярных языков, а также проверка принадлежности к регулярному языку, берут свое начало в [7]. Алгоритмы минимизации числа состояний ДКА появились в [5]. В работе [4] предложеннаиболее эффективный алгоритм нахождения минимального ДКА.1.Y. Bar-Hillel, M.
Perles, and E. Shamir, “On formal properties of simple phrase-structuregrammars,” Z. Phonetik. Spachwiss. Kommunikations-forsch. 14 (1961), pp. 143–172.2.S. Ginsburg and G. Rose, “Operations which preserve definability in languages,” J. ACM10:2 (1963), pp. 175–195. (Гинзбург С., Роуз Дж.
Об инвариантности классов языковотносительно некоторых преобразований. — Кибернетический сборник, Новая серия, вып. 5. — М.: Мир, 1968. — С. 138–166.)3.S. Ginsburg and E. H. Spanier, “Quotients of context-free languages,” J. ACM 10:4(1963), pp. 487–492.4.J. E.
Hopcroft, “An n log n algorithm for minimizing the states in a finite automaton,” inZ. Kohavi (ed.) The Theory of Machines and Computations, Academic Press, New York,pp. 189–196. (Хопкрофт Дж. Алгоритм для минимизации конечного автомата. —Кибернетический сборник, Новая серия, вып. 11. — М.: Мир, 1974. — С. 177–184.)5.D. A. Huffman, “The synthesis of sequential switching circuits,” J. Franklin Inst. 257:3-4(1954), pp. 161–190 and 275–303.6.S.
C. Kleene, “Representation of events in nerve nets and finite automata,” inC. E. Shannon and J. McCarthy, Automata Studies, Princeton Univ. Press, 1956, pp. 3–42.(Клини С.К. Представление событий в нервных сетях. — сб. “Автоматы”. —М.: ИЛ, 1956. — С. 15–67.)7.E. F. Moore, “Gedanken experiments on sequential machines,” in C. E. Shannon andJ. McCarthy, Automata Studies, Princeton Univ.
Press, 1956, pp. 129–153. (Мур Э.Ф.Умозрительные эксперименты с последовательностными машинами. — сб. “Автоматы”. — М.: ИЛ, 1956. — С. 179–210.)8.R. E. Stearns and J. Hartmanis, “Regularity-preserving modificationsexpressions,” Information and Control 6:1 (1963), pp. 55–69.9.J. I. Seiferas and R. McNaughton, “Regularity-preserving modifications,” TheoreticalComputer Science 2:2 (1976), pp.
147–154.184ofregularÃËÀÂÀ 4. ÑÂÎÉÑÒÂÀ ÐÅÃÓËßÐÍÛÕ ßÇÛÊÎÂ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
