Warum ist $ (AA) ^ * BB (AA) ^ * BB (AA) ^ *) ^ * $ von star-höhe 1

Question

Ein generalisierter regulärer Ausdruck ist wie ein regulärer Ausdruck, aber mit einem weiteren Betrieb erlaubt: Komplementierung. Die (verallgemeinerte) sternhöhe eines verallgemeinerten regulären Ausdrucks ist die maximale Anzahl verschachtelter Kleene-Sterne. Die Sternhöhe einer Sprache ist die minimale Sternhöhe eines regulären Ausdrucks, der es beschreibt. Es ist nicht bekannt, ob sogar eine Sprache der Sternhöhe 2 ist.

Ich stelle mir also vor, die LANGADE $ (AA) ^ * BB (AA) ^ * BB (AA) ^ *) ^ * (AA) ^ * $ von Wörtern, bestehend aus Verketten von $ AA $ und $ BB $ , mit einer geraden Anzahl der $ BB $ , ist von generalisierter Sternhöhe $ 1 $ . Aber ich konnte es nicht beweisen. In der Zeitung einige Ergebnisse auf der allgemeinen sternhöhe probleme (pin, straubing, thérien), lemma 6.1 (das transfer lemma) kann nicht angewendet werden, da sowohl $ (BB) ^ * $ und $ (AA) ^ * $ sind von sternhöhe 1.

Ich habe an anderer Stelle einige Sprachen gesehen, die zu einer Sternhöhe 2 waren, und sie waren komplexer als die, die ich gebe, also ist es sehr wahrscheinlich von Sternhöhe 1. Ist es der Fall?

Answer 1

(Dies ist ein Versuch, eine Antwort zu beantworten, ich hoffe, dass die Details richtig sind.)

Ihre Sprache besteht aus allen Zeichenfolgen in $ (AA + BB) ^ * $ mit einer geraden Anzahl von $ BB $ .

Wir dürfen Komplementierung verwenden, sodass wir mit dem Erkomplement der Sprache beginnen. Ich denke, wir können die Ergänzung in zwei (überlappende) Teile aufteilen

.
• Saiten nicht aus dem Formular $ (AA + BB) ^ * $ , diese Sprache hat starhöhe eins.
• Zeichenfolgen des Formulars $ w_0 \ cdot bb \ cdot w_1 \ cdot bb \ cdot w_2 \ dots bb \ cdot w_n $ , wobei (1) die Anzahl von $ BB $ ist ungerade, und (2) der $ w_i $ enthalten keine $ BB $ (aber ich muss genauer darauf sein)

Jetzt versuchen wir, einen Ausdruck für die Sprache $ W $ des $ w_i $ ohne Stern zu verwenden. Das heißt, wir können den Stern verwenden, um die ungerade Anzahl von $ BB $ , wie in $ (W \ CDOT BB \ cdot w \ cdot bb) ^ * \ cdot w \ cdot bb \ cdot w $ .

Dies ist der schwierige Teil. Saiten von $ W $ sind entweder

.
• Die leere Zeichenfolge $ \ VAREPSILON $
• nur ein einziger $ A $
• des Formulars $ AXA $ , wobei $ A $ nicht $ BB $ . Nicht "mit $ BB $ " ist die Ergänzung von $ (A + B) ^ * BB (A + B) ^ * $ , und wie Sie wissen, dass $ (a + b) ^ * $ wieder sternfrei ist.

Die Saiten, die wir jetzt angegeben haben, können längere Dehnungen von $ B $ haben, aber wann immer dies passiert, so dass der $ vorhanden ist B $ kommen paarweise.