Questions tagged [automata]
Questions about mathematical devices that read an input stream symbol by symbol and use a state transition map to produce an output stream, maybe using secondary storage.
1,842 questions
2
votes
1
answer
70
views
Stateless Modeling of Stochastic Systems
Let $f : S \times \mathbb{N} → \mathbb{Z}$ be a stochastic function seeded by $\mathrm{seed} \in S$, constrained such that
$$
|f(\mathrm{seed}, t + 1) - f(\mathrm{seed}, t)| \le 1
$$
Such a function ...
- 163
2
votes
0
answers
62
views
Statement on regular language density
On this forum, I've found following statement on densities of regular languages:
The density of a regular language is of the form $\Theta \left( n^k \lambda ^ n \right)$ for some integer $k \geq 0$ ...
- 21
1
vote
0
answers
54
views
Stronger version of the Pumping lemma for context-free languages
Prove the following stronger form of the pumping lemma, wherein both pieces v and y must be nonempty when the string s is broken up.
If A is a context-free language, then there is a number k where, if ...
- 13
0
votes
1
answer
65
views
If Σ* union with CFL/CSL etc still gives Σ*, is language always regular?
I have language of form wxwᵗ where w ∈ {a,b}* and x ∈ {a,b}* . If I take w = ε then it becomes x, and since x ∈ {a,b}* this gives Σ*. Other cases like wwᵗ (CFL) or wwwᵗ (CSL) also appear, but union ...
- 91
2
votes
0
answers
67
views
Number of non-isomorphic Moore machines with less than four states
does somebody know how to derive a formula for the number of non-isomorphic Moore machines with less than four states and binary input alphabet and binary output alphabet?
- 191
-1
votes
2
answers
100
views
Design a context-free grammar that accepts the language of all binary strings with at most one occurrence of 000
Idea: either no “000”, or exactly one “000” with no other “000” before/after and no overlap across the boundary.
Can someone pls help?I'd really appreciate.
- 1
1
vote
1
answer
105
views
Conversion of AFA to NFA; definition of NFA transition function
This question has been asked here in the community before. I wanted to follow up on the definition of the transition function used for the constructed NFA.
For all levels $X$ in the run tree of AFA, ...
0
votes
0
answers
70
views
Is it decidable whether a Turing machine modifies the tape or moves left a specific number of times on a given input?
I'm trying to understand whether the following languages are decidable or undecidable, and why. I would appreciate a clear explanation of the reasoning process, especially regarding how a machine's ...
- 181
0
votes
1
answer
102
views
Proving Relationship Between Modified Grammar and Homomorphism: How to Formulate the Right Lemma?
Suppose I have a context-free grammar
$$
G = (V, \Sigma, S, R)
$$
generating a language $L$.
I define a new grammar
$$
G' = (V \cup \{\sigma\}, \Sigma \setminus \{\sigma\}, S, R \cup \{\sigma \to \...
- 181
3
votes
2
answers
735
views
Connection between finite state machines and algorithms
One of my favourite topics from university was automata theory and formal languages — is there a word that encompasses both? I understand its use in verification, requirements and safety engineering, ...
- 39
6
votes
1
answer
247
views
How do I construct an FSA that accepts the non-fixed points of a finite state transducer?
Given a finite state transducer $F$, I'm interested in constructing a finite state automaton that accepts the set of input strings $x$ such that $F(x) \ne x$.
My questions are:
Is this set always a ...
- 63
0
votes
1
answer
79
views
Why is the complement CFL?
I have this language:
$L = \{a^nb^nc^kd^k∣n > k\}$
I get why $L$ isn't context free, but why $\bar{L}$ context free?
- 101
0
votes
1
answer
113
views
What strings does this DFA accept?
I'm trying to figure out the strings that are accepted by this DFA. I noticed that if there are at least 2 consecutive a's, the string will be accepted. But, I'm not sure how to expand on that. I'm ...
- 11
1
vote
1
answer
95
views
Encoding Universal Reachability in an NFA as a SAT Problem
I am working on encoding a reachability problem for a non-deterministic finite automaton (NFA) as a SAT problem. The NFA has multiple start states and a single final state. My goal is to find a ...
- 13
0
votes
0
answers
31
views
Designing a 3-state Turing Machine Equivalent to a Given Machine [duplicate]
Assume we have a Turing machine $M = (Q, \Sigma, \Gamma, \delta, q_0, B, F)$, where $|Q| = k$, that recognizes the language $L(M)$.
I want to design another Turing machine $M'$ that satisfies $L(M') = ...
- 367