11
votes
Accepted
Does there exist a unique minimal DFA with more than one start state?
Even a small extension of the deterministic model towards a nondeterministic one results in the complexity of minimization to jump from $\text{P}$ to $\text{NP-complete}$. For example, allowing two ...
- 4,874
9
votes
Does there exist a unique minimal DFA with more than one start state?
Consider the language $L = a\mid \Sigma^*b$. If I am not mistaken, the minimal DFA has the following transition table:
$$\begin{array}{|c|c|c|}
\hline
& a & b\\
\hline
\rightarrow q_0 & ...
- 17k
4
votes
Accepted
Can one prove directly that the language given by a regular grammar is the language given by some regular expression?
Let $G = (\Sigma, V, P, S)$ a context-free grammar.
Let us start with some simple statements:
Lemma 1: $G$ is right-regular (rules $X\to \varepsilon$, $X\to a$ and $X\to aY$ only) if and only if it is ...
- 17k
2
votes
Can one prove directly that the language given by a regular grammar is the language given by some regular expression?
Here's a solution using language equations.
With every grammar $G$ with terminals $\Sigma$, non-terminals $V = \{S_1, S_2, ..., S_n\}$ and start variable $S_1$ we can associate a system of equations ...
- 1,624
1
vote
Can one prove directly that the language given by a regular grammar is the language given by some regular expression?
There is not much difference (technically) between a nonderterministic automaton and a linear grammar. A single step from state to state reading a letter is equivalent to a nonterminal generating a ...
- 31.1k
Only top scored, non community-wiki answers of a minimum length are eligible