All Questions
Tagged with finite-automata or automata
2,105 questions
- Bountied 0
- Unanswered
- Frequent
- Score
- Trending
- Week
- Month
- Unanswered (my tags)
1
vote
2
answers
89
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:
...
0
votes
0
answers
51
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, ...
2
votes
2
answers
62
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):
...
0
votes
1
answer
50
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
97
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
42
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, ...
5
votes
0
answers
186
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 ...
0
votes
0
answers
23
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 ...
5
votes
1
answer
272
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 ...
0
votes
0
answers
56
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 ...
0
votes
0
answers
104
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 ...
0
votes
0
answers
39
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) ...
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 ...
2
votes
0
answers
59
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 ...
1
vote
2
answers
79
views
Pumping Lemma - string partitioning
Given the language $A=\{(01)^n|n\in\mathbb{N}\}$. The following attempt for a proof of its irregularity was outlined: "Suppose for the sake of contradiction that $A$ is regular. Thus, it has some ...