Частный автомат
В информатике , в частности в теории формального языка , факторавтомат может быть получен из заданного недетерминированного конечного автомата путем соединения некоторых его состояний. Фактор распознает надмножество данного автомата; в некоторых случаях, регулируемых теоремой Майхилла-Нерода , оба языка равны.
Формальное определение
[ редактировать ](Недетерминированный) конечный автомат — это пятерка A = ⟨ Σ , S , s 0 , δ , S f ⟩, где:
- Σ — входной алфавит (конечный непустой набор символов),
- S — конечное непустое множество состояний,
- s 0 – начальное состояние, элемент S ,
- δ перехода состояний — отношение : δ ⊆ S × Σ × S , и
- S f — множество конечных состояний, (возможно, пустое) S. подмножество [ 1 ] [ примечание 1 ]
Строка a 1 ... a n ∈ Σ * распознается A , если существуют состояния s 1 , ..., s n ∈ S такие, что ⟨ s i -1 , a i , s i ⟩ ∈ δ для i =1,..., n и s n ∈ С ф . Набор всех строк, распознаваемых A , называется языком , распознаваемым A ; он обозначается как L ( A ).
Для отношения эквивалентности ≈ на множестве S состояний A A фактор-автомат / ≈ = ⟨ Σ , S / ≈ , [ s 0 ], δ / ≈ , S f / ≈ ⟩ определяется формулой [ 2 ] : 5
- входной алфавит Σ такой же, как у A ,
- множество состояний S / ≈ является множеством всех классов эквивалентности состояний из S ,
- начальное состояние [ s 0 ] является классом эквивалентности начального состояния A ,
- отношение перехода состояний δ / ≈ определяется как δ / ≈ ([ s ], a ,[ t ]), если δ ( s , a , t ) для некоторых s ∈ [ s ] и t ∈ [ t ], и
- множество финальных состояний S f / ≈ — это множество всех классов эквивалентности финальных состояний из S f .
Процесс вычисления A / ≈ также называется факторизацией A по ≈.
Пример
[ редактировать ]| Автомат диаграмма |
Признанный язык |
Является ли частное | |||
|---|---|---|---|---|---|
| Автор : | Б по | С по | |||
| А : | 
|
1+10+100 | |||
| Б : | 
|
1 * +1 * 0+1 * 00 | a≈b | ||
| С : | 
|
1 * 0 * | a≈b, c≈d | c≈d | |
| Д : | 
|
(0+1) * | a≈b≈c≈d | a≈c≈d | a≈c |
Например, автомат А, показанный в первой строке таблицы [ примечание 2 ] формально определяется
- С А = {0,1},
- С А = {а, б, в, г},
- с А
0 = а, - д А = { ⟨a,1,b⟩, ⟨b,0,c⟩, ⟨c,0,d⟩ }, и
- С А
е = {б, в, г}.
Он распознает конечный набор строк { 1, 10, 100 }; этот набор также можно обозначить регулярным выражением «1+10+100».
Отношение (≈) = { ⟨a,a⟩, ⟨a,b⟩, ⟨b,a⟩, ⟨b,b⟩, ⟨c,c⟩, ⟨c,d⟩, ⟨d,c⟩, ⟨ d,d⟩ }, более кратко обозначаемый как a≈b,c≈d, представляет собой отношение эквивалентности на множестве {a,b,c,d} автомата A. состояний Построение частного A по этому отношению приводит к появлению автомата C в третьей строке таблицы; формально определяется
- С С = {0,1},
- С С = {а, с}, [ примечание 3 ]
- с С
0 = а, - д С = { ⟨a,1,a⟩, ⟨a,0,c⟩, ⟨c,0,c⟩ }, и
- С С
е = {а,с}.
Он распознает конечное множество всех строк, состоящих из произвольного числа единиц, за которыми следует произвольное количество нулей, т.е. ... }; это множество также можно обозначить регулярным выражением «1 * 0 * ". Неформально, C можно представить как результат A, приклеивая состояние a к состоянию b и приклеивая состояние c к состоянию d.
В таблице показаны еще некоторые фактор-отношения, такие как B = A / a≈b и D = C / a≈c .
Характеристики
[ редактировать ]- Для каждого автомата A и каждого отношения эквивалентности ≈ на его множестве состояний L ( A / ≈ ) является надмножеством (или равным) L ( A ). [ 2 ] : 6
- Для конечного автомата A над некоторым алфавитом Σ можно определить отношение эквивалентности ≈. на Σ * по x ≈ y, если ∀ z ∈ Σ * : xz ∈ L ( А ) ↔ yz ∈ L ( А ). По -Нерода теореме Майхилла A / ≈ является детерминированным автоматом, распознающим тот же язык, что A. и [ 1 ] : 65–66 Как следствие, фактор A по каждому уточнению ≈ также распознает тот же язык, что и A .
См. также
[ редактировать ]Примечания
[ редактировать ]- ^ Хопкрофт и Ульман (раздел 2.3, стр. 20) используют слегка отклоняющееся определение δ , а именно. как функция от S × Σ к набору степеней S .
- ^ На схемах автоматов в таблице символы из входного алфавита и названия штатов окрашены в цвет зеленый и красный соответственно; конечные состояния нарисованы двойными кружками.
- ^ Строго формально, набор S С = {[а], [б], [в], [г] } = { [а], [в] }. Скобки классов опущены для удобства чтения.
Ссылки
[ редактировать ]- ^ Jump up to: а б Джон Э. Хопкрофт ; Джеффри Д. Уллман (1979). Введение в теорию автоматов, языки и вычисления . Ридинг/Массачусетс: Аддисон-Уэсли. ISBN 0-201-02988-Х .
- ^ Jump up to: а б Тристан ле Галль и Бертран Жанне (март 2007 г.). Анализ взаимодействия бесконечных автоматов с использованием решетчатых автоматов (PDF) (внутренняя публикация). Институт исследований в области компьютерных наук и случайных систем (IRISA) — кампус Университета Болье. ISSN 1166-8687 .