Questions tagged [automata]

Automata Theory, including abstract machines, grammars, parsing, grammatical inference, transducers, and finite-state techniques

426 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
8
votes
0answers
167 views

Unambiguous formal grammars for a specific class of languages

Suppose that $w \in \{0; 1\}^*$ is a binary word. Let's denote the number of $0$-s in $w$ as $\#_0(w)$ and the number of $1$-s in $w$ as $\#_1(w)$. Now suppose that $q \in \mathbb{Q}$ is a positive ...
5
votes
0answers
66 views

Proving associativity of addition with weird carry operation

There is a somewhat famous example of group cohomology witnessing $\mathbb{Z}/100$ as an extension of $\mathbb{Z}/10$ by $\mathbb{Z}/10$, with the standard carry function $c$ as a 2-cocycle (cf. this ...
5
votes
0answers
190 views

Can we decide if a dragon comes home?

First, a quick definition: A (deterministic) Lindenmayer system (L-system) over an alphabet $\mathcal{A}$ is essentially specified by a function $f:\mathcal{A}\mapsto\mathcal{A}^*$ (where $\mathcal{A}^...
5
votes
1answer
142 views

Proving that a language is not context-free

Given the language $$L = \{ a^p \mid p\, \text{IS NOT prime} \}$$ is $L$ Context free? If not, prove that it's not. May I have some suggestions on how to use the pumping lemma to prove this, please? ...
4
votes
0answers
77 views

Is the set of pushdown transductions closed under composition?

Let’s define a pushdown transducer as a 9-tuple $V = (A, B, S, Q_A, Q_S, \phi, \psi, \chi, q_0)$, where $A$ is the finite input alphabet, $B$ is the finite output alphabet, $S$ is the finite stack ...
4
votes
1answer
2k views

NFA of $k$ states recognizing all words of length $\le k$

Let $N$ be an NFA with $k$ states that recognizes some language $A$. a. Show that if $A$ is nonempty, $A$ contains some string of length at most $k$. b. Show, by giving an example, that part (a) is ...
4
votes
0answers
1k views

NFA to DFA conversion

I am trying to convert the following NFA to an equivalent DFA: My steps: There is an $\varepsilon$-transition from $q_0$ to $q_1$, hence the set of initial states is $\{q_0,q_1\}$. From $\{q_0,q_1\}$...
4
votes
1answer
235 views

Is the Champernowne constant an automatic number?

The Champernowne constant in base $b \geq 2$ is obtained by concatenating the $b$-ary expansion of every integer. For example, in base $10$ this is $$ 0.123456789101112131415\dotsc $$ Question: Is the ...
4
votes
2answers
100 views

Showing that 2 languages are context free

I have these 2 languages: $$L_1 = \left\{a^ib^jc^k: k\ge i+j\right\}\\ L_2 = \left\{w_1cw_2 : w_1,w_2\in\{a,b\}^\ast\land |w_1|_a = |w_2|_a\right\}$$ How can I determine that they are context free ...
3
votes
0answers
57 views

Finite State Automata

it's been a while since I've done FSA's so I'm a little rusty, bear with me. I'm creating an FSA to parse Integer and Decimal tokens for a class. The two tokens have the regex Integer: $0|[1-9][0-9]^*$...
3
votes
1answer
63 views

Characterization of recognizable submonoids

Suppose $M$ is a finitely generated monoid. A subset $X \subseteq M$ is said to be recognizable if there exists a homomorphism $\varphi : M \to K$ to some finite monoid $K$ satisfying $X = \varphi^{-1}...
3
votes
0answers
147 views

Open problems in Cellular Automata field

here there is a link on Wolfram about 20 open problems of CA theory. Has anyone of them been solved or tested? I'm searching for literature.
3
votes
0answers
296 views

How to show $L = \{a^n b^m c^p: n\neq m\} \cup \{a^n b^m c^p: m\neq p\}$ is ambiguous?

I'm recently familiar with this site and prefer to ask a very hard problem :) How can we prove that the following language is inherently ambiguous? $$L = \{a^n b^m c^p: n\neq m\} \cup \{a^n b^m ...
3
votes
0answers
359 views

nth-root of continued fraction with Raney transducers

There are some algorithms for doing basic arithmetic by using regular continued fraction expansions. These algorithms are mainly due to Gosper (1972) and Raney (1973). These two approaches use (bi)...
3
votes
0answers
607 views

Converting a pushdown automaton (that accepts by final state) to a context-free grammar

Given the following PDA: $$ P = (\{q, p\}, \{0, 1\}, \{Z_0, X\}, \delta, q, Z_0, \{p\}) $$ where the transition function $\delta$ is given by: $$ \delta(q, 0, Z_0) = \{(q, XZ_0)\} \\ \delta(q, 0, X)...
3
votes
0answers
89 views

Size of automata or regular expressions avoiding cross patterns

Let $\Sigma$ be an alphabet of finite size $k$, and $n$ some integer. I am interested in the language of words of size $n$ that do not contain $abab$ as a subword, for any pair $(a,b) \in \Sigma$ (I ...
3
votes
0answers
69 views

Lattice worms with nontrivial deaths

In Paterson's worms, a triangular lattice is used. A worm can move in 6 directions. As each node is hit, the worm follows an internal rule for which edge it will eat next based on the edges already ...
3
votes
1answer
116 views

Determine the language that corresponds to the following automata.

I want to determine that language that corresponds to the following automata Note: $q_{6}$ have arrow to $a$ to himself. I started with the minimal words: $aaabb$ $aaba$ $aaaba$ $bababa$ the only ...
3
votes
1answer
3k views

My Moore and Mealy machines look the same. Why?

For university I have to construct equivalent Mealy and Moore machines that solve certain problems. But I am confused, as my Moore and Mealy machines turn out to have exactly the same nodes, just with ...
2
votes
0answers
22 views

$w = 0001000 \in L'$, but this $w$ is not in $L$?

Suppose if $L ⊆ Σ^∗$ is a regular language then the following language is also regular: $$L' = \{w\mid ∃x, y ∈ Σ^∗ : w = xy ∧ yx ∈ L\}$$ For a simple example, let L be given by the regular expression $...
2
votes
0answers
24 views

Is pushdown transduction of a periodic sequence periodic?

Let’s define a pushdown transducer as a 9-tuple $V = (A, B, S, Q_A, Q_S, \phi, \psi, \chi, q_0)$, where $A$ is the finite input alphabet, $B$ is the finite output alphabet, $S$ is the finite stack ...
2
votes
1answer
52 views

Is this considered a regular expression?

I need to design an NFA that recognizes the language $L$, with alphabet $\{a,b\}$, that accepts strings that: have length at least 4 two letters before the final letter of the string there is always ...
2
votes
0answers
105 views

Given two languages L1 and L2, how to calculate L1\L2

I have a problem with my paper recently. For a given language $L_1$, which is generated by a deterministic finite automaton(DFA) $G$. For another language $L_2$, which is generated by an ...
2
votes
0answers
83 views

How is the prime number theorem used here?

I have come across two papers that invoke the prime number theorem, without actually explaining how exactly they arrive at their conclusions. The claims in question are highlighted in bold. First ...
2
votes
0answers
27 views

$k$-generated finite groups as transducer groups for $k$-state transducers

Let’s define a transducer as a $5$-tuple $(Q, A, B, \phi, \psi)$, where $Q$ is the collection of states, $A$ is the input alphabet, $\phi: Q\times A \to Q$ is the transition function and $\psi: Q \...
2
votes
0answers
29 views

$\mathcal{L}_1 = \{\text{Strings with a 1 at a multiple of 3 from the front}\} $ and …

$$\mathcal{L}_1 = \{\text{Strings with a 1 at a multiple of 3 from the front}\} $$ and $$\mathcal{L}_2 = \{\text{Strings with a 1 at a multiple of 3 from the end}\}$$ I need to design a DFA for these....
2
votes
1answer
41 views

Proving with the pumping lemma that the following language is not regular

I want to prove that $A$ = {ww: w $\in \sum^{*}$} is not regular. This is what I have done so far: Suppose A is regular. Let $p$ be the constant that must exist if $A$ is regular. Then, we can ...
2
votes
0answers
155 views

Can every language of context-free grammar be expressed in set builder notation?

Is it true that every CFG can be written as CFL just by using set builder notation and basic algebraic terms? For example CFG named $G$: $$S \rightarrow a\,S\,b\,\,|\,\,\epsilon$$ Can be written as ...
2
votes
1answer
56 views

equivalent $NFA$s

I have a $NFA$ named $A$, with number of states $n$. And I got another $NFA$ name $B$ with number of states $k$. I want to check $L(A)=L(B)$. My question is how long should I go. What is the ...
2
votes
0answers
27 views

Generate a Pushdown Automaton that accepts the strings from the language $L=\{a^ib^jc^k, i + k \ne j\}$

I am trying to generate a Pushdown Automaton that accepts the strings of the language $L=\{a^i b^j c^k, i + k \ne j\}$. From this I know that the following situations can occur: $i + k < j$ or $i +...
2
votes
0answers
66 views

Does there exist a universal finite automaton?

I am having some trouble understanding what the question is asking me. Here is my understanding. We want to know whether or not there exists a DFA so that when I input a tuple $\langle D,w\rangle$, ...
2
votes
0answers
140 views

Pumping lemma: Convert pumped, binary string $xy^iz$to integer

I am trying to use the pumping lemma to prove that the language consisting of the set of $0$'s and $1$'s, beginning with a $1$, such that when interpreted as an integer, that integer is prime, is not ...
2
votes
0answers
34 views

Stochastic Generative Automaton Optimization

Let $S = \lbrace s_1,\dots,s_N\rbrace$ denote a set of states and $Y$ an output alphabet with $\vert Y\vert=K$. From a state $s_i$ you transition to state $s_j$ via an edge labeled with $y\in Y$ and a ...
2
votes
1answer
223 views

CFG for $L = \{{ ABC \ | \ A, B, C \in \{{0,1\}}^∗ \ ,\ |A| = |B| = |C| \ \ and \ \ A\neq C\}}$

I need to find a CFG for $L = \{{ ABC \ | \ A, B, C \in \{{0,1\}}^∗ \ ,\ |A| = |B| = |C| \ \ and \ \ A\neq C\}}$ but after a lot of attempts I have failed miserably. Could I get some directions?
2
votes
1answer
165 views

Two questions regarding one-counter automata

Let's assume we have a non-deterministic one-counter automaton without epsilon transitions. I have two questions: Is there an algorithm (if yes, what is it?) that answers whether this automaton ...
2
votes
0answers
396 views

Prove the Halting Problem is undecidable (using a reduction)

In Hopcroft, Motwani, and Ullman, "Introduction to Automata Theory, Languages, and Computation", 2nd edition there is the following problem. Prove that the halting problem is undecidable. I assume ...
2
votes
1answer
60 views

Is it possible to generate both path and cost in a state machine using a matrix?

I have a state machine where from each state you can only go to one other state. Furthermore, there is also a cost associated with certain state transitions (these costs are always $ \geq 0$ which ...
2
votes
0answers
312 views

Memory of finite automata

Let $\{0,1\}$ be the input alphabet of a finite Moore automaton and $n$ the number of its internal states. When for each binary input sequence of length $k$ after being applied to the initial state ...
2
votes
0answers
1k views

Regular expression for string's of a's and b's beginning with b and not having two consecutive a's

Question: Write a regular expression for the following language: "All strings of a's and b's in ∑* beginning with b and not having two consecutive a's. A textbook says the answer is (b+ba)*. Shouldn'...
2
votes
0answers
50 views

Let $LOOP_{TM}$ be descriptor language of all touring machines that won't halt for any input. Show reduction of $HALT_{TM}$ to $LOOP_{TM}$

Question from Homework that I'm having difficult to answer on: Let $LOOP_{TM} = \{\langle M\rangle \mid \text{M is a TM that does not halt on any input w}\}$ Let $LOOP_{TM}$ be descriptor language of ...
2
votes
1answer
201 views

Finding regular expressions for which a given Turing machine halts and accepts, halts and rejects, and diverges.

Consider the Turing machine M = (Q,Σ,Γ,δ,q,F) F = {t} Q = {q,r,s,t,v,x} Σ = {a,b,c} Γ = {B,a,b,c} δ = [q,a,q,a,R] [q,b,q,b,R] [q,c,v,b,R] [q,B,r,B,L] [r,a,s,B,L] [r,b,s,B,L] [r,c,s,B,L] [s,a,x,a,...
2
votes
0answers
122 views

Trouble with induction on the length of a word

In the accepted solution of the question If L is regular, prove that $\sqrt{L}=\{w:ww\in L\}$ is regular the answerer made the claim that "What's left is to show that $δ ′ (q_{0}' ,w)=h$ , which can ...
2
votes
0answers
58 views

show that language is regular

Let $B_n = \{a^k\ |\text{ where } k\text{ is a multiple of } n\}$. Show that for each $n\ge 1$ the $B_n$ language is regular. My proposition of solution: What about it ?
2
votes
1answer
234 views

Intersection of context-free language and its reversal

I know that intersection of two context-free languages is not always context-free and the following problem: Given two context-free languages A and B, is $A \bigcap B \neq \emptyset$ ? is ...
2
votes
1answer
590 views

Minimal DFA for a given regular expression

How can I construct a minimal DFA from the following definition? $L=\{w \in \{a,b,c\}^* $: if the second-to-last letter from w is an $a$, then the number of $c$'s $\le 1\}$ I've already made a ...
2
votes
1answer
1k views

Pumping Lemma for regular languages proof template

http://www.cs.uiuc.edu/class/fa06/cs273/Lectures/pumping-lemma/pumping-lemma.html So, I went to that site and it says: $w = xyz$ $|xy| \leq p$ $|y| \geq 1$ for all $i$, $xy^iz$ is in $L$. ...
2
votes
1answer
131 views

Context free grammar for language

I'm learning how to generate context-free grammar for a language. $L=\{{a}^i {b}^j {c}^k\, |\,i=j\lor j=k$ Here is how I tried ...
2
votes
0answers
147 views

halting problem

Prove that it is undecidable for the halting problem of a deterministic Turing machine which accepts nonrecursive language or in-other-words: let's say we have a deterministic Turing machine which ...

1
2 3 4 5
9