People who code: we want your input. Take the Survey

Tag Info

4

Keith Ellul, Bryan Krawetz, Jeffrey Shallit and Ming-wei Wang constructed, in their paper Regular Expressions: New Results and Open Problem, a regular expression of size $O(n)$ for which the minimal rejected word has size $\Omega(n2^n)$; here $n$ is an arbitrary parameter. The regular expression can be converted to an NFA with $O(n)$ states and transitions ...

3

LALR(1) is the grammar obtained by merging states of CLR(1). The states with the exact same production rules i.e. the exact same core, but different lookahead are combined together. Specifically, consider $$I_i: A\rightarrow \alpha \bullet \beta, \; a \;\; \mbox{and}\;\; I_j: A\rightarrow \alpha \bullet \beta, \; b$$ The merged state looks like I_{ij}: A\...

2

The Canonical LR algorithm is not more powerful with respect to languages. The set of languages which have CLR grammars is exactly the same as the set of languages recognised by LALR grammars, or even by SLR grammars. There are CLR grammars which not LALR. So the CLR algorithm applies to more grammars. But for any such grammar it is possible to construct an ...

2

Your question is solved in Cezar Câmpeanu and Wing Hong Ho, The Maximum State Complexity for Finite Languages, Corollary 10.

2

The operator $Z(L) = \{ x \mid xww\in L \text{ for some } w\}$ takes strings from the original language $L$ but keeps only prefixes $x$ that are obtained by chopping a suffix of the form $ww$. This is a special application of the right quotient operation: $L/K = \{ x \mid xy\in L \text{ for some } y\in K\}$. It is known that the family of regular languages ...

2

Let $A = (Q, \delta, q_0, F)$ a DFA that accepts $L$. For $q, q' \in Q$, define: $L_{q,q'} = \{u\in \Sigma^*, \delta^*(q, u) = q'\}$; $L_{q',F} = \{u\in \Sigma^*, \delta^*(q', u) \in F\}$. It is quite easy (can you prove it?) to see that those languages are regular. Now the language $\{x\in \Sigma^*\mid \exists w\in\Sigma^*, xww\in L\}$ can be written as: $... 1 Try to use an online graph editor, like this one. In the settings set it to have directed edges and custom labels, and type a triplet$(s_1,s_2,v)$for an edge from$s_1$to$s_2$with$v$written on the edge. However, this won't allow you to create "accepting" states, when you draw this yourself, add them by hand... If you prefer a slightly worse-... 1 To elaborate on the method described by Yuval in the comment, first, construct a DFA with output as follows: Let the state space be$Q=\{q_i \mid 0 \le i \le 9\}$, and input and output alphabet be$\Sigma = \{i \mid 0 \le i \le 9\}$. The initial state would be$q_0$. Let the DFA read the decimal number in reverse. For any state$q_i$, on reading$d$, you ... 1 Your first approach doesn't quite work. If it is not the case that for any$k$there is some language that requires exactly$k$states, then all you know is that there exists a single$n$such that every$n\$-state DFA can be reduced to an equivalent DFA with fewer states. The second approach does work, and requires a lower bound technique such as the pumping ...

Only top voted, non community-wiki answers of a minimum length are eligible