Questions tagged [finite-automata]
Questions about finite automata, an elementary automaton model with finite memory. It is equivalent to regular languages and the basis for many more complex models.
-1
votes
0answers
17 views
How to precisely know whether a language is regular ? , a regular expression can be generated for it ? , as well as dfa? [duplicate]
I feel difficulty in finding whether a language is regular and also is regular expression can be generated ??
Please anyone let me know about all the possible cases.
This will help me very much..
0
votes
1answer
21 views
Why does an extended transition function not work if the string does not result in a final state? [on hold]
If I am not wrong a string is only accepted by a finite automata if the string results in a final state.
Why is that?
With symbols we can transition into another non-final state, why is that not ...
2
votes
2answers
42 views
Is the language L = {(a,b)* | #a * #b is an odd number} regular?
Is the following language regular? $$\{ w \in \{a, b\}^* |\ \text{the product of the number of $a$'s and the number of $b$'s is an odd number}\} $$
If i'm not mistaken the condition is the same as ...
2
votes
1answer
17 views
Polynomial-time Compute the Number of States resulting from the NFA to DFA (greedy) conversion?
The canonical NFA to DFA conversion, starting with an NFA with $n$ states, can result in a DFA with $2^n$ states. However, in many cases, there are states that are "unnecessary," such as when ...
2
votes
1answer
42 views
Construct a DFA from the regular expression (a)*+(aab)*
I've broken down the expression into two simpler DFAs but right now I'm stuck.
I don't know what to do with the expression a*, my solution currently (as presented above) is a NFA, not DFA.
2
votes
1answer
12 views
Proving a language comprised of 2 languages is regular(with suffix and prefix)
I am having hard time proving that the following language,comprised from two regular languages $L_1,L_2$(over the same $\Sigma$)is indeed regular:
$$L^\frown = \{ w\in \Sigma^* | w=u\sigma_1\mu_1...\...
4
votes
1answer
17 views
Proving a language comprised of 2 languages is regular
So glad to find this place. I have been struggling for quite a while with this given question and i am not sure how to fully address it.
The question:
$L_1$ and $L_2$ are regular languages over the ...
1
vote
0answers
25 views
Tree languages regular
Let $T_1,T_2 \subseteq T_\Sigma$ be regular tree languages, f a symbol with arity 2.
To proof: $\{f(t_1,t_2) \mid t_1 \in T_1, t_2 \in T_2\} \subseteq T_{\Sigma \cup \{f\} }$ is regular.
So it's ...
1
vote
1answer
50 views
Construction of a Deterministic Tree Automaton (DTA)
Let $L \subseteq \Sigma^*$ be a regular language. Let $\Sigma' = \Sigma_0 \cup \Sigma_2$ where $\Sigma_0 =\Sigma$ and $\Sigma_2=\{*\}$.
We define $T_L=\{t \in t_{\Sigma'} \mid \text{The leafs from t ...
2
votes
1answer
61 views
Finding a regular expression of a language
Our alphabet is {a,b} and we need to find a regular expression for the language of all words of the form $a^*b^*$, which their length is a product of 3 (meaning their length is divisible by 3).
...
1
vote
0answers
56 views
What is the word “madness” doing in the first chapter's title of Automata Theory, Languages and Computation by Hopcroft, Motwani, Ullman?
The chapter's title is "Automata: The Methods and the Madness". This title came along in the second edition and remains in the third edition. In the first edition, the the second chapter's title is "...
1
vote
1answer
31 views
In which reference can I find a definition for the equivalence of DFAs?
How is the equivalence of DFA defined? I found the equivalence of states --- James Hein, section 5.3, page 301. But he doesn't define equivalence between entire automata. (Ullman and Hopcropft seem ...
0
votes
0answers
26 views
Using Nerode theorem to prove that the following languages are non-regular
I've been trying to understand the idea behind proving a language is not regular by using Nerode's theorem, but I just couldn't apply the idea on what I've been asked.
The problem is to prove the ...
1
vote
1answer
32 views
Efficiently deciding whether TM accepts all inputs in at most $k$ steps
I want to decide if a deterministic TM $A=(Q, \varGamma, \delta, q_s, q_h)$ halts on every input in at most $k$ steps. If the TM $A$ stops after $k$ steps, then the positions $A$ can reach are ...
1
vote
3answers
55 views
DFA for a language that accepts the addition of multiple of 2 and multiple of 5
I am trying to draw a DFA that accepts the following language:
$L=\{a^{2i+5j} : i , j \geq 0\}$
I started out by drawing an NFA, which I can then convert to a DFA but I am not sure if my NFA is ...
1
vote
1answer
71 views
NFA that accepts all numbers not divisible by 105
I have to create an NFA that accepts the following language L with no more than 15 states.
$L = \{a^n \mid n \geq 1$ and $n \mod105 \neq 0 \}$.
To me it seems that all multiples of 105 have the ...
0
votes
1answer
37 views
Recognizing Regular Languages in Layman terms [duplicate]
I understand that regular languages are languages which can be computed by Finite Automata however i am having some trouble understanding how one can identify a regular from non-regular.
I know that ...
9
votes
1answer
1k views
Non-deterministic Finite Automata | Sipser Example 1.16
I am working through the Sipser Book (2nd edition) and came across this example, which I do not understand. In the book it states that this NFA accepts the empty string, $\epsilon$.
Could someone run ...
0
votes
1answer
42 views
Dana Angluin's L* algorithm - Hypothesis inconsistent
is it possible for the Dana Angluin's L* algorithm that a hypothesis is inconsistent?
So assume we have a closded observation table for a regular language L. Now after creating the hypothesis we will ...
1
vote
1answer
38 views
DFA multiple accepting states to Regular expression
I am trying to find the regular expression that defines this DFA, I am finding this particular case difficult since it has multiple accepting states.
If I understand this DFA correctly, it recognises:...
0
votes
2answers
49 views
Prove that the following language is regular [duplicate]
Let L1, L2 be regular languages. And let A1=〈Σ,Q,q0,𝛿1,F1), A2=〈Σ,P,p0,𝛿2,F2) be their DFA.
Prove that the following language is regular, by making an appropriate NFA for it:
𝐿3={𝜎1𝜎1′𝜎2𝜎2′…𝜎...
3
votes
1answer
36 views
ε-NFA to DFA - initial state with only epsilon transitions
I am having trouble discovering how to convert a ε-NFA to DFA (image below) when all transitions in the initial state are epsilon transitions. I already know how to convert ε-NFA to DFA (common cases),...
1
vote
0answers
26 views
Computational power of quantum finite automata
I am preparing some lecture notes on the computational power of quantum finite automata (QFA). I am a bit confused about which models of QFA are stronger and which models are weaker than standard ...
2
votes
2answers
56 views
Pumping lemma occurrence of c > d
I'm trying to prove a language is not regular through using pumping lemma, but can't seem to come up with any way of doing it.
The alphabet is:
$$ \Sigma = \{c, d\} $$
The language is:
$$ A = \{z ...
2
votes
1answer
41 views
The order of ε-transitions in NFA
I'm reading 'Introduction to the Theory of Computation' by Michael Sipser. He gives an example of a NFA, stating that this particular automaton accepts $a$ (he lists other strings as well, I just want ...
2
votes
1answer
48 views
Help with question from Sipser chapter 1
Is this language regular?
$0^k10^k \ with \ k\geq1$
It needs to count the starting and ending zeros which is impossible with finite states.
Update:
This is the whole problem from the book:
Let $\...
3
votes
0answers
38 views
Tree Automata Operators
I am trying to understand the Projection operation (linear tree homomorphism) and Cylindrification operation (inverse tree homomorphism) from the book. Linear Tree homomorphism is defined as follows:
...
0
votes
1answer
27 views
How to show a language is regular through creating DFA
I'm trying to prove that a given language is regular through proving that a DFA can be created from it, but have problems with how to the DFA should look.
The alphabet is $\Sigma=\{0, 1\}$ and the ...
-1
votes
1answer
72 views
Backtracking in DFA [closed]
Is it true that backtracking is allowed in deterministic finite automaton (as mentioned in many comparisons between DFA and NDFA)? If yes, how is it possible when transition in DFA is to a single ...
0
votes
1answer
63 views
Limitations of DFA [duplicate]
In this link it is mentioned:
A DFA is not powerful enough to recognize many context-free languages because a DFA can't count.
But counting is not enough -- consider a language of ...
1
vote
1answer
39 views
Simple property of DFAs
Do you know if this simple property of a DFA is stated as a property (or theorem) in some Automata theory book (possibly with a particular name)?
Property: Given a DFA $A = \{ Q, \Sigma, \delta, q_0, ...
1
vote
1answer
33 views
How to check if DFA is actually a correct model of the intended system?
Suppose I have modeled a deterministic finite automaton of my system. How can I check if the traces generated by this system, actually represent the model I had in mind?
For example, say I have DFA ...
1
vote
1answer
49 views
Why are those very similar languages in a different complexity class?
i am having a real time understand why the following two languages are in two different complexity classes(the first is NP-Hard and the second is in P). tried to look online at various resources and ...
0
votes
3answers
85 views
Define a finite automaton accepting the language below [duplicate]
$\{ w∈(a,b)^\ast | w $ does not contain '$ab$' as a subword $\}$.
About questions like this, I always want to construct the regular expression for it, then convert the regular expression to a finite ...
2
votes
1answer
30 views
State Transition Diagrams for XOR
I have found two different versions for State Transition Diagrams for XOR.
I'm confused as to why one has 2 states and the other has 3. What are the implied states in each please?
Are they both ...
1
vote
0answers
33 views
Characterization of NFA whose equivalent (minimal) DFA has exponential number of states
(I don't know if there are standard names for this, so) Let's say that a Nondeterministic Finite Automaton (NFA) is $n$-expansive if it has $n$ states and any Deterministic Finite Automaton (DFA) ...
2
votes
1answer
18 views
Modelling regex replacement via a DFA
I wish to model the following common construction in code via a finite state automaton for the purposes of static analysis:
...
2
votes
2answers
47 views
Is intersection used in regular expression?
As union is part of regular expression in form of positive closure, similarly intersection is also a part of regular expression? in which form it can be used?
0
votes
0answers
63 views
How to find the minimum number of states of a deterministic finite automaton accepting a given language [duplicate]
Let
$L$ be a language over $\Sigma$. And $\Sigma = \{0,1\}$ is a set of input alphabets.
$L = \{ w \mid w \in \Sigma^*, \text{ where $w$ is a string with numbers of 0s divisible by 3 and number of ...
0
votes
0answers
15 views
Arden theorem with 3 input [duplicate]
I have just started learning Arden's theorem to convert finite automata but I am stuck on its execution when we have 3 inputs.
Because I am not able to simplify any equation to have only 2 inputs ...
1
vote
1answer
50 views
Brzozowki's algorithm doesn't work for this corner case
I'm a newbee learning DFA minimization. And I found that(strangely) Brzozowki's algorithm cannot give me a minimized DFA on this example:
In this DFA, $S_0$ and $S_1$ are nondistinguishable and ...
3
votes
1answer
88 views
Is the language of words with equal number of 010s and 101s as substrings regular?
Is the language of words containing same number of 101s and 010s regular?
If yes, how can I design a DFA for it?
In general, is the language of words containing equal number of strings which one is "...
1
vote
3answers
67 views
Is it possible to define a DFA for the language of words having exactly one double letter? [closed]
Consider the language $\{ w \in \Sigma^*~|~ w~\text{contains exactly one double letter}~\}$. For example,
$baaba$ has exactly one double letter, but $baaaba$ has two double letters.
Suggested answer ...
0
votes
0answers
54 views
proving DFA stuck
This DFA fulfills:
Define a function $diff: \{0,1\}^*\to\Bbb Z$, for $w \in\{0,1\}^*$, $diff(w)=($# of 1's in $w)- ($# of 0's in $w$).
Thus, $diff(\epsilon)=0$; $diff(0)=−1$; $diff(1)=1$.
Let $L = ...
6
votes
2answers
1k views
Is there a reasonable and studied concept of reduction between regular languages?
Have been any interesting formulations for the concept of reduction between regular langauges, and if so -- are there regular-complete languages under those reductions?
0
votes
0answers
34 views
dfa subtract multiple of 3 [duplicate]
Define a function 𝑑𝑖𝑓𝑓 ∈{0,1}→ℤ so: for everything w ∈{0,1}, diff w = # of 1's in w- # of 0's in w.
Thus:
𝑑𝑖𝑓𝑓 𝜀=0;
𝑑𝑖𝑓𝑓 0=−1;
𝑑𝑖𝑓𝑓 0=−1;
Let 𝐿 = {𝑤∈ {0,1} * | 𝑑𝑖𝑓𝑓 𝑤 = 3𝑚 ...
3
votes
2answers
79 views
One counter automaton as a function
We can associate a one counter finite automaton with a function $f:\Sigma^* \to \mathbb{N} \times \{0,1\}$, where $f(x)=(n,b)$ describes the state where the automaton terminates when fed an input word ...
0
votes
0answers
12 views
How to understand DFA's and how to understand how to construct them based on a given regular language? [duplicate]
I have practiced DFA's for an upcoming test and I haven't been able to grasp how to construct more difficult DFA's. An example would be this question : Construct a deterministic finite state automata ...
4
votes
1answer
264 views
Irregularity of language of prefixes of decimal expansion of pi
Let $L_{\pi}$ be the language consisting of prefixes of the decimal expansion of $\pi$:
$$L_\pi = \{3, 31, 314, 3141, 31415, 314159, \ldots\}.$$
Prove that Lπ is not DFA-recognizable. You may use the ...
1
vote
1answer
29 views
Do all DFA's containing an “accepting path containing a cycle” accept infinite languages?
So I've seen this claim being made on different questions:
Do self-loops in DFA cause infinite languages?
I'd like to find formal proof for this.
I think I should also note that an "accepting path ...
