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

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.

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 A * jest tuż jednolita , jeżeli dla wszystkich u , v ∈ M , u , u , v ∈ M oznacza v ∈ M . $M$$A^*$$u, v \in M$$u, uv \in M$$v \in M$

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

1. jest właściwym jednostkowym submonoidem,$L$
2. dla jakiegoś kodu prefiksu P ,$L = P^*$$P$
3. Minimalny automat ma unikalny stan końcowy, a mianowicie stan początkowy.$L$
4. 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 A ∗ . Następujące warunki są równoważne:$L$$A^*$

1. jest wolnym submonoidem A ∗ ,$L$$A^*$
2. dla jakiegoś kodu C ,$L = C^*$$C$
3. $L$

$L$$A^*$

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

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

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

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.