6

Here is a proposition for an elementary proof: Let $\mathcal A=(A,Q,q_0,F,\delta)$ be a DFA for $L$, we want to build a DFA $\mathcal A'=(A,Q',q_0',F',\delta')$ for $f^{-1}(L)$. Intuitively, when reading a word $u$, $\mathcal A'$ will remember the state reached in $\mathcal A$ by $f(u)$, together with the action of $u$ on all states of $\mathcal A$. More ...


5

$\beta(E_1)$ is the language $s^nx,s^{n+1}x$. This language is straightforwardly not regular, by the pumping lemma. If we assume that the language is regular, the pumping lemma tells us that there must exist some $p, q$ such that for all $n \ge p$, $s^{n+q}x,s^{n+1}x$ is also in the language. This is false, meaning that the language is not regular. A similar ...


4

Regarding question (1): As long as $k$ is $\Omega(n^c)$ for some $c > 0$, then the problem is $PSPACE$-complete. See this paper by Klaus-Jörn Lange and Peter Rossmanith (1992) for some related results. https://doi.org/10.1007/3-540-55808-X_33 Regarding question (2): Say that the intersection problem is parameterized by the number of FSA's. If this ...


4

An algebraic characterisation of the restricted temporal logic (fragment using only next and eventually, but not until) is given in [1]. The expressive power of this fragment is the set of regular languages whose syntactic monoid are locally $\cal L$-trivial. I am not sure of the result you are looking for, but this article probably contains enough material ...


3

This is #P hard via counting solution to monotone DNF formula. Let $\phi(x_1,...x_n)$ be monotone DNF formula on $n$ variables. We are trying to find regular language $L$ over alphabet $\{0,1\}$ with all words of length $n$ and the words in $L$ are in one to one correspondence with the satisfying assignment of $\phi$. Variable $x_i$ in $\phi$ corresponds to $...


2

Lemma 1. Consider $L = (ab)^* + (ba)^*$: There exists CFG with two variables which generates $L$ There exist no CFG with one variable which generates $L$ For proving (1) we may just consider the following CFG $$ S \rightarrow bAa \mid A , \, A \rightarrow abA \mid \varepsilon$$ The second proposition is a bit more tricky. Suppose that there exists CFG $G = ...


1

After more and more digging, here is what I found: First reference: Introduction to Automata Theory, Languages, and Computation 3rd Edition. Specifically, theorem 4.26 indicates that the provided algorithm constructs a minimum state machine M for a A such that M has as few states as any DFA equivalent to A. This was my original understanding, so the answer ...


1

You mean the worst-case complexity of computing NFAs accepting $L(\mathcal{A}) \cup L(\mathcal{B})$ and $L(\mathcal{A}) \cap L(\mathcal{B})$? For union it's easy to achieve $O\left(|Q_A| + |Q_B|\right)$ as we need to add new initial state $q_{\ast}$ and add transitions of kind $(q_{\ast}, a, q)$ whether $(q_{i_A}, a, q) \in \Delta_A$ or $(q_{i_B}, a, q) \in \...


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