7

The precise bound is $2^n$. The lower bound was given in the comments: the state complexity of $A^*a_1A^* \cap \dotsm \cap A^*a_nA^*$ is $2^n$. For the upper bound, it suffices to observe that if $B$ and $C$ are subsets of the alphabet $A$, then the language $B^*CA^* = (B - C)^*CA^*$ is recognised by a 2-state DFA. It follows that the complexity of the ...


6

Lamine commented on the connection to the Chomsky-Schützenberger enumeration theorem. Recently, a few research problems in formal language theory were solved using continuous mathematics via this connection. For example: Hermann Gruber, Jonathan Lee, and Jeffrey Shallit. Enumerating Regular Expressions and their Languages. available online at arxiv.org as ...


6

The precise answer depends on your model of PDA (models differ among different authors; compare Sipser to Hopcroft &Ullman). And number of states alone is not a good measure for PDA's, because there is a well-known tradeoff between states and stack symbols. For example, a classic construction turns a grammar like $S \rightarrow X_1 X_1$ $X_1 \...


6

It seems it would depend on your particular model, in particular what information you have access to. From what I infer, you are thinking of the following model: you have a memory $m$, for instance of size $O(\log n)$. at each step, you read a new letter $a\in\Sigma$ of your stream, and you are allowed to modify your memory $m$ you then have to say whether ...


6

Short answer: it depends on how you set the acceptance condition of the DPDA model: final state or empty stack. The endmarkers are not necessary for DPDAs in which the accept condition is final state (which is also used to define the deterministic context-free languages - DCFLs): for all $L \dashv$ ("endmarked" language) recognized by a DPDA there is a DPDA ...


5

This model is one of the standard models in automata theory and it has been examined by some researchers. The references given in the first comment are very good starting points. When the head is two-way, the classes of languages recognized by such models are identical to logarithmic-space classes. However, when the head is one-way, then, up to my ...


5

(Answer inspired by Lamine's comment) We assume the automaton is only allowed to push one symbol per state (otherwise, you could make the stack arbitrarily large with only two states). With a stack alphabet of size $k$, we can construct an automaton that accepts a word of length $O(n^{k+c})$. The basic idea is to just make the stack as large as possible, ...


5

One of the first connections is via generating functions. The Chomsky-Schützenberger theorem states that the generating function of the number of words of a unambiguous CFL is algebraic. In his paper, Flajolet proves that several CFL are inherently ambiguous by showing that their generating function is transcendental (their “local behavior” around their ...


5

Pavlovic et al. view Turing machines over a binary alphabet as coalgebras for the functor $\lambda X. \, 2 \times \mathcal{P}_{\mathrm{fin}}(X \times 2 \times \{\lhd,\rhd\})^2$. The symbols $\lhd$ and $\rhd$ represent thereby the tape moves. Bart Jacobs has presented in "Coalgebraic walks, in quantum and Turing computation" an approach by using a monad. He ...


4

I view this question as one in the history of Turing machine theory, which indeed has had more changes than are evident from contemporary textbooks. The Turing model of 1936 was remarkably different from the later more accepted formulations. In more detail in terms of your questions: (1),(2) The modern formulation in terms of Recogniser, and Languages ...


4

Let $L$ be the set of powers of 2 encoded in base 3. The encoding of $4^n$ in base 3 ends with 1, whereas the encoding of $2\cdot 4^n$ in base 3 ends with 2. Hence $L' = L \cap \Sigma^*1$ is the encoding of all powers of 4. The encoding of an integer $m > 0$ in base 3 takes $\lceil \log_3 (m+1) \rceil$ digits. Since neither $4^n$ nor $4^n+1$ are powers ...


4

Yes, this is a compactness property. Let $X$ be the region you want to tile, and $T$ the finite set of possible tiles. The space $T^X$ of all assignments of tiles to $X$ is compact by Tychonoff’s theorem. For any finite $X_0\subseteq X$, the set $C_{X_0}\subseteq T^X$ of all correct tilings of $X_0$ is closed (in fact, clopen), and since $C_{X_0\cup X_1}\...


4

Yes, there are lots of automata models for processing XML: I recommend you look into (extensions of) finite tree automata, see e.g. this text book as an intro https://www.worldcat.org/title/foundations-of-xml-processing-the-tree-automata-approach/oclc/692197553 As a basis for building tools check out libvata for a c++ library that handles finite tree ...


3

I think you are describing a pushdown automaton: https://en.wikipedia.org/wiki/Pushdown_automaton


3

The following paper: http://www.faculty.idc.ac.il/udiboker/files/AutomataTypes.pdf shows that the intersection (and union) of deterministic parity automata may involve an exponential blowup. Thus, you cannot do much better than converting to nondeterministic Buchi automata, and taking the intersection there (and determinizing back to parity).


3

In a 1967 pager, Al Rosenberg gave the example of a language which is deterministic linear time but not deterministic quasi-realtime that Book & Greibach probably refer to. Rosenberg mentions that such examples were published previously by himself and Cole.


2

This seems to be exactly the type of question studied by Moses Ganardi and coauthors in recent years. In particular this paper and this extension prove nice trichotomies.


2

Can we have more than one Deterministic Finite Automata (DFA) diagrams for a set of strings? Of course! There's also an algorithm to minimize a deterministic finite automata into a minimal deterministic finite automata. The existence of such algorithm is a proof that for most, if not all, sets of strings, many DFAs can be defined.


2

In the standard $\epsilon$-free PDA definition the transition function is: $\sigma : Q \times \Sigma \times \Gamma \to Q \times \Gamma^*$ $(q_i, a, A, q_j, \alpha) \in \sigma$ means that the PDA on state $q_i$, with head on input $a$ and $A \in \Gamma$ on top of the stack, enters state $q_j$ and replace $A$ with $\alpha \in \Gamma^*$ According to this ...


2

Assuming we have an unbounded stack and pointers, it's a Turing machine. Since the stack is unbounded, we can get by very easily using a CPS-like style. Whenever we need to allocate memory, we'll just do it on a stack frame, then continue with the computation on the next. If our stack frames were bounded in size, of course we'd be a finite state machine. ...


2

As mentioned in the comments, if you allow some extra additive slack of $\varepsilon\in(0,1]$ (an input parameter) in the error guarantee, and relax the success probability from one to $1-\delta$ (another input parameter), then the question becomes equivalent to agnostic PAC-learning the class $\mathcal{C}_n$ of $n$-state DFAs with membership queries. ...


2

First, there is an infinite tiling of the plane if and only if there are square tilings $$ T_1 < T_2 < T_3 < \ ... $$ such that $T_i$ is an $i \times i$ square tiling, and $T_i$ is a subtiling of $T_{i+1}$. Now, for each $T_i$ define $f(T_i)$ to be the size of the largest square tiling that $T_i$ is a subtiling of, where $f(T_i) = \infty$ if for ...


1

I found a partial answer to question 2. The same idea is discussed in the last 10 minutes of this lecture.


1

As mentioned in the comments, regular grammars are more or less a (string) rewriting system, where the arrow of a derivation is in the reverse direction of the rewriting arrow. Since you seem to be especially interested in term rewriting systems (as opposed to string rewriting systems), the automaton model that you are probably looking for is that of tree ...


1

Mark Gold indeed proved this very claim in his seminal paper "Language Identification in the Limit". This quite a well-known result now. You can find more on this in Colin de La Higuera's book on Grammatical Inference.


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