Generalized star height problem
Statement
Let be a finite alphabet. The set of generalized regular expressions over is defined inductively: and for each are generalized regular expressions, and if and are generalized regular expressions, then so are , , and . The language denoted by such an expression is given by , , , , , and .
The star height of a generalized regular expression is defined by
For a regular language , its generalized star height is
Then: for every finite alphabet and every regular language ,
that is, can be denoted by a generalized regular expression in which no Kleene star occurs inside the scope of another Kleene star.
Record
- Added
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 inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.