ProbXiv
Explorersign in
Problem archiveProblem record

Statement

Let AA be a finite alphabet. The set of generalized regular expressions over AA is defined inductively: ∅\emptyset and aa for each a∈Aa \in A are generalized regular expressions, and if EE and FF are generalized regular expressions, then so are (E∪F)(E \cup F), (E⋅F)(E \cdot F), (E∗)(E^{*}) and (Ec)(E^{c}). The language L(E)⊆A∗L(E) \subseteq A^{*} denoted by such an expression is given by L(∅)=∅L(\emptyset) = \emptyset, L(a)={a}L(a) = \{a\}, L(E∪F)=L(E)∪L(F)L(E \cup F) = L(E) \cup L(F), L(E⋅F)=L(E)L(F)={uv:u∈L(E), v∈L(F)}L(E \cdot F) = L(E)L(F) = \{uv : u \in L(E),\, v \in L(F)\}, L(E∗)=⋃n≥0L(E)nL(E^{*}) = \bigcup_{n \ge 0} L(E)^{n}, and L(Ec)=A∗∖L(E)L(E^{c}) = A^{*} \setminus L(E).

The star height h(E)h(E) of a generalized regular expression is defined by

h(∅)=h(a)=0,h(E∪F)=h(E⋅F)=max⁡{h(E),h(F)},h(Ec)=h(E),h(E∗)=h(E)+1.h(\emptyset) = h(a) = 0, \qquad h(E \cup F) = h(E \cdot F) = \max\{h(E), h(F)\}, \qquad h(E^{c}) = h(E), \qquad h(E^{*}) = h(E) + 1 .

For a regular language L⊆A∗L \subseteq A^{*}, its generalized star height is

gh(L)=min⁡{h(E):E a generalized regular expression over A with L(E)=L}.\mathrm{gh}(L) = \min \{ h(E) : E \text{ a generalized regular expression over } A \text{ with } L(E) = L \} .

Then: for every finite alphabet AA and every regular language L⊆A∗L \subseteq A^{*},

gh(L)≤1,\mathrm{gh}(L) \le 1 ,

that is, LL can be denoted by a generalized regular expression in which no Kleene star occurs inside the scope of another Kleene star.

Record

Added
Links

Comments

Nothing has been published against this problem yet, and nothing has been said about it.

Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.

Sign in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.