Questions tagged [automata]
Automata Theory, including abstract machines, grammars, parsing, grammatical inference, transducers, and finite-state techniques
2,104 questions
0 votes
0 answers
36 views
Minimal Fixed Point of Set of Regular Expression Equations
I'm reading The Theory of Parsing, Translation, and Compiling (1972) by Aho and Ullman and came to the part about equations with regular expressions for coefficients and variables. I'm having trouble ...
1 vote
2 answers
112 views
How does this CFG enforce the inequality $0^a 1^b 0^c$ where $a < b + c$ and $a, b, c \geq 0$?
I am studying Context-free Languages, and my professor gave as homework the following language $$ 0^a 1^b 0^c \quad where \quad a < b + c \quad and \quad a,b,c \ge 0 $$ My friend gave this answer: ...
- 97
0 votes
0 answers
56 views
Proving whether a language L is regular or not using the pumping lemma (and some intuition)
"For a symbol a, define a+ = {a,aa,...}. Is the language L = {wcwR|w,c ∈ {a,b}+} regular? Here, wR is just w reversed. If your answer is yes, write the equivalent regular expression, and if no, ...
- 191
2 votes
2 answers
64 views
SageMath's Automaton method number_of_words error
Consider the language of those $w\in \{a,b,c,d\}^*$ that contain $ab$. Corresponding DFA is (written in SageMath): ...
- 12.7k
0 votes
1 answer
51 views
Which one is the correct CFG for the strings?
Design a context-free grammar (CFG) that generates all strings over {a, b, c} that contain at least one 'a', one 'b', and one 'c'. Define the rules of the CFG. So I wrote this down: S -> aXbXc | ...
0 votes
1 answer
105 views
Decidability of there is a word that is accepted by a TM in fewer steps than the length of the word
I was presented with this question: L = {<$M$> | There is a word $x$ that is accepted by $M$ in fewer than $|x|$ steps} I think that this is not decidable, and my immediate thought was to make a ...
0 votes
0 answers
43 views
What is an appropriate mathematical formalism to express the following?
Let $S$ be a set of states. Let $A$ be a set of actions. Let $f$ be a function $S \times A \to S$. For example, let $f$ be equal to $$\{((s_0, a_0), s_0), ((s_0, a_1), s_1), ((s_1, a_0), s_1), ((s_1, ...
- 325
5 votes
0 answers
199 views
Combinatorial proof of "ABRACADABRA" theorem
some time ago I stumbled upon a fact that the average first appearance of a sequence HH while randomly repeatedly generating flipping coins is higher than for example for HT. This for a fact depends ...
- 51
0 votes
0 answers
25 views
Pitfall in application of Strong Pumping lemma for Context free Languages
I am trying to apply the strong version of the pumping lemma for Context-Free Languages on the following language. $L = \{a^nb^n,n\geq1\}$ Let us assume there is a CFG $G$ which generates words in the ...
- 138
5 votes
1 answer
278 views
Efficient estimation of Perron–Frobenius eigenvalues for $\ell$-RLL constrained composite DNA without full matrix construction
I am studying constrained coding for composite DNA (based on arXiv:2501.10645), where each composite symbol represents a mixture of nucleotides. To enforce a maximum runlength $\ell$, they model valid ...
- 288
0 votes
0 answers
57 views
Valid application of the pumping lemma for regular languages?
My professor tends to prove a language L is not regular using contradiction, i.e: Assume L is regular $\implies$ L can be pumped Show that L cannot be pumped Contradiction, so initial assumption is ...
- 27
0 votes
0 answers
110 views
Intersection of 2 deterministic finite automatons (DFAs)
These are the two initial DFAs, and I need to construct a DFA that recognizes the intersection of the two languages accepted by the given DFAs, using closure properties. Here is the first DFA: And ...
- 9
0 votes
0 answers
41 views
Which States Satisfy the Hennessy–Milner Logic Formula $[ 𝑏 ] [ 𝑎 ] ⊥$ in This Labeled Transition System?
I'm working with a labeled transition system (LTS) that has four states $p_1, p_2, p_3, p_4$ and the following transitions: I want to determine which states satisfy the Hennessy–Milner Logic (HML) ...
- 35
0 votes
2 answers
87 views
When do we specify domains when it's implied?
I asked an AI about the language a^m b^n c^n d^m, and in replying to me, it translated that into $\{a^mb^nc^nd^m \mid m, n \geq 0\}$. Is this standard usage? I find it weird; negative integers make no ...
- 123
2 votes
0 answers
62 views
Tower of Hanoi Group is automata group
To describe the Tower of Hanoi game one can define the group of legal actions as an automata group, that is a finitely generated subgroup of the automorphism group of a regular rooted tree, which is ...
- 21