Questions tagged [finite-automata]
Questions about finite-state automata, an elementary computational model. When interpreting its semantics w.r.t finite words, then it captures the class of regular languages.
1,837 questions
0
votes
1
answer
16
views
Demonstrate that this language is regular using pumping lemma
I have to demonstrate that this language is regular.
The alphabet is A={a, b}.
L = {w in A*| w=a^k, k%n=0} with ...
- 11
5
votes
1
answer
627
views
Are definite languages closed under Kleene Star?
This question came up while solving a problem in a Language Automata textbook, in which a definite language is defined as:
"a language L is definite if there is a number k where for every string ...
- 53
2
votes
1
answer
126
views
How to find a bijection $\Phi$ that maximizes the number of iterative replacements in a local rewriting system on $\left\{ 0, 1, 2, 3 \right\}$?
Problem. We study a local rewriting map defined on $5$-letter words over the alphabet $\{0,1,2,3\}$. A fixed forbidden-block set $\mathcal{F}$ of $16$ length-$3$ patterns is given by
$$\mathcal{F}= \{...
- 111
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, ...
5
votes
1
answer
112
views
Number of states of a 2DFA from n-state 2NFA
2NFA and 2DFA here are two-way finite automata, equivalent to a read-only Turing Machine.
Naively, I thought there would be $2^{2n}$ states in the equivalent 2DFA, assuming a subset construction is ...
2
votes
2
answers
178
views
Proving α₂ ≤ α₁ + |w| + 1 for Myhill-Nerode equivalence classes when adding a word w to a regular language
Let $\Sigma$ be a finite alphabet and let $L_1 \subseteq \Sigma^{\ast}$ be a
regular language. Pick a word $w \in \Sigma^{\ast}$ and define
$$
L_2 := L_1 \cup \{w\}.
$$
For $i \in \{1,2\}$ let $\...
- 21
-2
votes
1
answer
70
views
Intro to cs,please choose the correct option
. Let the finite automaton ( A ) be
[ A = { (q_0, q_1), (a, b), q_0, \delta, (q_1) }, ]
where
[ \delta(q_0, a) = { q_1 }, ]
[ \delta(q_1, a) = { q_0 }, ]
[ \delta(q_1, b) = { q_0, q_1 }. ]
A.) The ...
1
vote
1
answer
70
views
How to Perform Structural Synthesis of a Nondeterministic Moore Machine? (Diagram Attached)
Good afternoon! I have a functional diagram of the Moore NFA machine, a system of canonical equations and output functions of the Moore machine, and a table of direct transitions.
I have a question ...
- 11
0
votes
1
answer
93
views
How does an non deterministic PDA compute?
This is the PDA of the language
$L=\{ww^{R}:w\in\left(0\cup1\right)^{*}\}$
Where $w^{R}$ is the reverse of string.
Let $s=0110$ be the string, clearly $s\in L$. My query is as follows,
My query:-
PDA ...
- 179
0
votes
1
answer
77
views
How do you construct an even linear grammar from a finite automaton?
Even linear languages are defined in On a family of linear languages.
These languages are generated by special linear grammars, called even linear grammars (ELG), having only rules of the form
$A \to ...
- 2,068
-1
votes
1
answer
195
views
Does the "regular" in "regular expression" have the same terminology as the "regular" in "regular language"?
According to this post:
Mathematicians have a habit of hijacking common nouns and adjectives for mathematical objects and properties, sometimes with good reasons such as geometric or other analogies ...
- 1
4
votes
2
answers
166
views
Determinize History-Deterministic Automaton By Pruning
A known result is that History-Deterministic automaton for finite words contains a deterministic automaton that accepts the same language.
Meaning, we can achieve a deterministic automaton for the ...
- 322
2
votes
1
answer
111
views
Can I obtain a polynomial size NFA with one epsilon transition from another NFA?
Suppose I have an NFA $N_1$. I want to convert it into another NFA $N_2$ such that for each state in $N_2$, the state has exactly one transition for each character in the alphabet and exactly one ...
- 71
0
votes
1
answer
65
views
Question in proof of NOTALLNFA in NSPACE(n)
Let us consider the language
ALLNFA={⟨A⟩∣A is an NFA and L(A)=Σ∗}
and its complement
NOTALLNFA={⟨A⟩∣A is an NFA and L(A)≠Σ∗}.
In the context of showing that $\text{NOTALL}_{\text{NFA}}$ is in $\textsf{...
1
vote
3
answers
100
views
Find a DFA with at most two states, fitting a description
For the given two DFAs,
say that the machines are $M_1$ and $M_2$, and the corresponding languages are $L_1$ and $L_2$.
I need to find a single DFA with at most two states which accepts $L_1\cup L_2$....
- 387