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
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 ...
