(N) DFA z tymi samymi stanami początkowymi / akceptującymi

13

Co wiadomo o klasie języków rozpoznawanych przez automaty skończone posiadające ten sam stan początkowy i akceptacji? Jest to właściwy podzbiór zwykłych języków (ponieważ każdy taki język zawiera pusty ciąg znaków), ale jak bardzo jest słaby? Czy istnieje prosta charakterystyka algebraiczna?

To samo dotyczy języków rozpoznawanych przez niedeterministyczne automaty posiadające ten sam zestaw stanów początkowych i przyjmujących.

— Noam Zeilberger
źródło

13

Zakładając, że oznacza to, że stan początkowy musi być unikalna akceptując stan, automaty skończone posiadające tej struktury odpowiadają języków wyrażeń regularnych formularza

, gdzie

jest pewne wyrażenie regularne.

r^{*}

$r^*$

r

$r$

— Huck Bennett

Ach, oczywiście. Dzięki! Jeśli chcesz opublikować ten komentarz jako odpowiedź, zaakceptuję go i zamknę pytanie.

— Noam Zeilberger,

8

To pytanie zostało rozwiązane dla automatów deterministycznych i dla jednoznacznych automatów w książce [1]

[1] J. Berstel, D. Perrin, C, Reutenauer, Codes and automata, tom. 129 Encyklopedii Matematyki i jej Zastosowań, Cambridge University Press, 2009.

W przypadku automatów deterministycznych charakterystykę podano w Twierdzeniu 3.2.5. Przypomnijmy, że submonoid z jest tuż jednolita , jeżeli dla wszystkich , oznacza . $M$ $A^*$ $u, v \in M$ $u, uv \in M$ $v \in M$

Propozycja . Niech będzie regularnym podzbiorem . Następujące warunki są równoważne: $L$ $A^*$

jest właściwym jednostkowym submonoidem, $L$

dla jakiegoś kodu prefiksu , $L = P^*$ $P$

Minimalny automat ma unikalny stan końcowy, a mianowicie stan początkowy. $L$

Istnieje deterministyczny automat rozpoznający posiadający stan początkowy jako unikalny stan końcowy. $L$

W przypadku jednoznacznych automatów charakterystyka wynika z Twierdzenia 4.2.2 i może być określona następująco:

Propozycja . Niech będzie regularnym podzbiorem . Następujące warunki są równoważne: $L$ $A^*$

jest wolnym submonoidem , $L$ $A^*$

dla jakiegoś kodu , $L = C^*$ $C$

$L$

$L$ $A^*$

— J.-E. Kołek
źródło

1

Być może warto przyjrzeć się jednomianowemu rozkładowi Eilenberga jednomianowego przedrostka zwykłych (racjonalnych w jego terminologii) języków. Nie mam ze sobą kopii tej książki, ale znajduje się ona gdzieś we wcześniejszych sekcjach Automata, Języki i maszyny, Tom A (1974).

— gdmclellan

1

@gdmclellan Masz całkowitą rację. Dokładnym odniesieniem jest rozdział. IV, propozycja 3.2.

— J.-E.

P

$P$

C

$C$

L = P^{*}

$L = P^*$

P

$P$

P

$P$

14

$r^∗$ $r$ $r^*$

$q_0, \ldots, q_n$ $q_0 = q_n$ $n = 0$ $q_0$

— Huck Bennett
źródło

2

r^{*}

$r^*$

(a, a b)^{*}

$(a, ab)^*$

2

L

$L$

L

$L$

α^{*}

$\alpha^*$

α

$\alpha$

@ J.-E.Pin: Tak, dziękuję, zaktualizowałem swoją odpowiedź.

— Huck Bennett

10

Ważną podklasą tej rodziny jest podklasa języków 0-odwracalnych. Język jest 0-odwracalny, jeśli odwrócenie minimalnego DFA dla języka jest również deterministyczne. Operacja cofania jest definiowana jako zamiana stanów początkowych i końcowych oraz odwracanie relacji krawędzi DFA. Oznacza to, że język odwracalny do 0 może mieć tylko jeden stan akceptacji. Twoje pytanie dodaje kolejne ograniczenie, że stan ten powinien być stanem początkowym. Twoje ograniczenie nie definiuje języków odwracalnych 0, ponieważ minimalny DFA dla tych języków może mieć różne stany początkowe i końcowe.

Klasa języków odwracalnych jest interesująca, ponieważ była jedną z pierwszych rodzin języków o nieskończenie wielu ciągach znaków, których można było się nauczyć tylko na podstawie pozytywnych przykładów. Praca Angluina zawiera również charakterystykę algebraiczną.

Inference of Reversible Languages , Dana Angluin, Journal of the ACM, 1982

— Vijay D.
źródło

1

Możesz odnieść się do automatów półksiężycowych, jak to ujmuje ich papier: „Automat półautomatyczny (SFA) jest automatem przycinania o niepowtarzalnym stanie początkowym, który jest równy unikatowemu stanowi końcowemu, w którym wszystkie cykle przechodzą przez stan początkowy ”. Odwołaj się do „HOLONOMICZNEGO ROZKŁADU AUTOMATYKI PÓŁOKWIATOWEJ” - Shubh Narayan Singh, KV Krishna.

— Viresh
źródło