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,428
questions
-1
votes
1answer
6 views
What’s the regex in this DFA graph?
Here is an example of DFA that can correspond to a regular expression. I am trying to write a correct regular expression to this graph, but I am not entirely sure whether my answer is correct or not. ...
0
votes
1answer
32 views
Why is the Turing machine rather than the finite automaton the main model for computation if computers have finite memory?
Any physical computational device clearly has finite memory. On the other hand the input can be external and could therefore potentially be infinite. This idea is perfectly captured by the ...
0
votes
1answer
82 views
Is the language of DFAs that accept at minima one string in $\{b, c\}^*$ decidable?
Let the language $K = \{\langle W \rangle: W \text{ is a DFA on } \{a, b, c\} \text{ and } L(W) \text{ contains at minima one string in } \{b, c\}^*\}$.
Is it sufficient to define $M$ as follow :
...
1
vote
1answer
35 views
Can converting NFA to DFA change the language?
In the context of studying the conversion from an NFA to the equivalent DFA, I came across the following NFA, which accepts all strings over the alphabet $\{0,1\}$ which contain $01$:
After I ...
7
votes
2answers
148 views
Minimal number of states for an NFA of all different words
Given $\Sigma =\{0,1,@\}$, I am looking at a language $L=\{u@v | u,v\in \{0,1\}^k\wedge u\neq v\}$. So $u,v$ have only $0,1$s, same length $k$, yet are different.
Also, for me $k$ is a known constant. ...
1
vote
1answer
34 views
Given two DFA's accepting the same language, does one have to refine the other?
I have a logical question that I can't quite crack:
Given two automata accepting the same language $L$, does one have to refine the other?
In other words, if $A_1$ and $A_2$ both accept $L$, with ...
1
vote
1answer
21 views
Is my regular expression and finite automata diagram for this state table correct?
So i have some theory of computer science homework and I'm struggling with this question currently. I am given the following automaton:
$Q = \{q_0,q_1\}$.
$\Sigma = \{a,b\}$.
$q_0 = q_0$.
$F = \{q_0\}...
-2
votes
2answers
17 views
Regular expression of an FA
If we convert an NFA to a DFA, is the regular expression of the DFA the same as the NFA?
I know the difference between an NFA and DFA and the algorithm to convert an NFA to DFA
0
votes
2answers
55 views
Build an FA that accepts only the words baa, ab, and abb and no other strings longer or shorter
I have been trying solve this problem for a while now for a university assignment. I'm required to build a DFA and an NFA for the above question. So far I have been able to solve the DFA but can not ...
2
votes
1answer
50 views
Closure of regular languages under interchanging two different letters
Given any deterministic finite state automata $M$ over any alphabet, I need to construct an FSA $M'$ that accepts the set of strings $M$ accepts, but with two different letters interchanged. For ...
2
votes
1answer
42 views
Is there a bound on possible Dead state in a minimized DFA
I want to know if a DFA is minimized, is there an upper bound on how many dead states are possible when it is in its minimal form, in terms of number of states, etc?
Intuitively, I am thinking that it ...
3
votes
2answers
389 views
Irregularity of $\{ w_1 aa w_2 \mid |w_1| \neq |w_2| \}$
I'm currently struggling to come up with a proof that the following language is irregular:
$$L_2 := \{w_1aaw_2 \in \Sigma^* \mid w_1, w_2\in\Sigma^* \land |w_1| \ne |w_2|\}$$
where $\Sigma = \{a, b\}$....
1
vote
1answer
34 views
Finite automaton whose alphabet is $\mathbb{N}$
Is it possible to have a finite automaton where $\Sigma = \mathbb{N}$? Why or why not?
I think it is possible to have a set of all natural numbers, however I'm not sure why.
3
votes
1answer
31 views
Worst-Case Complexity of Quantifiers in Thompson's Construction
My understanding is that an NFA compiled using Thompson's Construction should have a running time that is linear in the length of the input string, with a space complexity that is linear with the ...
2
votes
1answer
410 views
NFA for words which start and end with different letters with $O(\log(| \Sigma |))$ states
I'm trying to build a NFA for the following language
$ L = \{ \sigma_1 \sigma_2 \sigma _3 \ldots \sigma _n \mid \sigma _1 \neq \sigma _n \}$.
The catch is that for $ \Sigma $ such that $ |\Sigma|=2^k $...
2
votes
1answer
61 views
Is $\{\varepsilon\}$ a conventional way to mark the empty language?
I am grading an exercise in Automata and Formal Languages and see many of the students use $\{\varepsilon\}$ as the empty language. At first I thought this was an error, and I have asked the lecturer ...
0
votes
1answer
19 views
Converting along regular expression to NFA
I have the following regular expression for the set of all strings such that each block of five consecutive symbols contains exactly two 0's (consider the alphabet to be {0, 1}):
(0+1+ϵ)4+(11100+ϵ)r(...
0
votes
1answer
19 views
NFA: each block of five consecutive characters contains at least two 0's
How can I find an NFA for such a language, considering the alphabet to be {0, 1}. I've tried deriving it from the DFA (@Steven) and the regular expression (@Yuval Filmus), but no luck.
2
votes
0answers
41 views
In what bases is the language $a^n$ regular?
Given $a\in\mathbb{N}$, I wondered for what bases $b$ is the following language regular
$$\{a_ka_{k-1}\ldots a_0\mid \exists n\in\mathbb{N},\ a_0+a_1b+a_2b^2+\ldots+a_kb^k=a^n\}$$
I think it's regular ...
0
votes
0answers
19 views
Are there more succint algorithm for translating NFA's to DFA's?
When translating an NFA to its deterministic equivalent, we get an exponential blowup due to the powerset construction method. I tried to search but couldn't find an appropriate question regarding ...
0
votes
0answers
19 views
How to describe this language a* (ba (cf* (g ( f +h )* bf* )* e )* a* )* in words?
I was task to describe this regular expression a* (ba (cf* (g ( f +h )* bf* )* e )* a)* informally.
My attempt at describing it informally = any number of a followed by any number of one b one ...
0
votes
1answer
84 views
Understanding lemma found in proof of quotient construction for DFAs
Lemma 13.6 $p \in F \Longleftrightarrow [p] \in F'$
Proof. The direction $\Rightarrow$ is immediate from the definition of $F'$. For the direction $\Leftarrow$, we need to show that if $p \approx q$...
0
votes
1answer
22 views
Give the Regular-Expression (NFA) with specific Separation Patterns
Question:
Given the RE (or NFA) for the set of all strings over $\Sigma ={a,b}$ such that: a occurs the odd number of times and each pair of a are separated by exactly $2n+2,n\geq 0$ b's.
Attempt:
...
1
vote
1answer
33 views
Doubt in understanding the time complexities of algorithms to recognize regular expressions
I was going through the text Compilers: Principles, Techniques and Tools by Ullman et. al first edition where I came across the following table.
The authors justify the table as follows:
Given a ...
0
votes
1answer
36 views
How do I apply the Pumping Lemma to prove that this language is not regular?
I am trying to teach myself Automata theory. I have hard time with the Pumping Lemma, so I am trying to work through examples. I stumbled upon this example, but it doesn't have steps how to solve it.
...
0
votes
0answers
39 views
Co-relating the direct algo for $\epsilon-NFA$ to $DFA$ with the chain : $\epsilon-NFA \rightarrow NFA \rightarrow DFA$
I was going through the text : Compilers: Principles, Techniques and Tools by Ullman et. al where I came across the following algorithm to convert an $\epsilon\text{-NFA}$ to $\text{DFA}$
...
1
vote
1answer
47 views
Finding infinitely many Myhill–Nerode equivalence classes [duplicate]
I need to prove the following languages are not regular and I'm having a
tough time identifying the equivalence class that can have an infinite
index.
How would I go about doing these? I know how to ...
1
vote
1answer
52 views
Regular languages closed under prefix operation
Suppose that $D$ is a regular language over an alphabet $A$. How can I prove that the following language is also regular?
$$ \mathrm{LANGUAGE}_2(D) := \{ d \mid d,t \in A^* \text{ and } dt \in D \} $$
...
0
votes
1answer
45 views
Prove no DFA with four states can accept L={111}
Assume we have a language L={111}. Prove no DFA with four states can accept L.
Can’t a DFA with 4 states accept L?
1
vote
1answer
36 views
Using Myhill Nerode to prove that a language is not regular [duplicate]
Prove that the language $A$ on $\{0,1\}$ containing all words for which the number of $0$s is equal to the number of $1$s is not regular.
I know one way to do it would be to show that the cardinality ...
1
vote
1answer
43 views
Myhill–Nerode equivalence classes of $\{0^n1^n \mid n \in \mathbb{N}\}$
I am told to find the equivalence classes of the Myhill–Nerode relation of the language $\{0^n1^n \mid n \in \mathbb{N}\}$. For one, I know it has an infinite number of equivalence classes given that ...
1
vote
1answer
62 views
Explaining NFA in words
I have an NFA, and the question I am asked is :
Let 𝑎 < 𝑏 < 𝑐. Now in simple English, express the language of the NFA to explain what type of strings are accepted by it.
In simple English, my ...
0
votes
1answer
38 views
When can a deterministic finite-state-automaton (DFSA) along with its input sequence be said to be a part of another DFSA?
For a Finite State Automaton / Finite State Machine (FSM) $F$, that has an input alphabet, a set of possible states, an initial state, a set of possible final states and a state transition function, ...
1
vote
1answer
50 views
Finite automaton for all words whose length $n$ satisfies $\operatorname{gcd}(n,504) \geq 6$
I have been working on the following homework question, and I just can't seem to make any progress:
Construct a finite automaton having fewer than 36 states that recognizes the language $\{s \in a^* :...
1
vote
2answers
51 views
Constructing a NFA from a regular expression
I have the following regular expression $R=ab^*(\epsilon \cup c) \cup c^*a$ and I want to construct the NFA that accepts languages defined by that regular expression.
I started by constructing the NFA ...
1
vote
1answer
42 views
Constructing a NFA that accept complement of language L of another NFA
if given a language $L$ recognized by NFA $N_0$ over an alphabet $\Sigma$. Is it possible to find a general way of constructing an NFA $N_1$ that accept $L^C$ such that $L^C= \{w \in \Sigma^{*} |\mid ...
1
vote
0answers
17 views
How to efficiently flatten a hierarchical state machine?
David Harel's StateCharts introduces hierarchical states and history mechanism, which are really powerful when modeling complex system behaviour. But when doing model based testing we need a "...
0
votes
2answers
45 views
Finite loop on a NFA
I understand that in a non-deterministic automaton, an input can lead to one, more than one, or no transition for a given state.
Given this information, I would assume that if the input lead to a loop,...
0
votes
1answer
36 views
new language accepted by FA when new transitions are added to a FA?
found this question online and I am trying to solve this question. I have solved this question but I think I might be missing some cases. Could someone verify if my answers are correct?
Let N = (Σ ∪ {...
0
votes
0answers
19 views
If L is a regular language, then the particular L′ is also regular? [duplicate]
Show that if $L ⊆ Σ^∗$ is a regular language then the following language is also regular:
$$L' = \{w\mid ∃x, y ∈ Σ^∗ : w = xy ∧ yx ∈ L\}$$
Can you give me a hint how to solve that?
1
vote
1answer
36 views
What is difference between Hidden Markov Model and Non-deterministic Finite-State Machine?
As the question implies, can you mention any difference between Hidden Markov Model and Non-deterministic Finite-State Machine? Are they different or the same?
1
vote
1answer
21 views
How does a transition function behave in a FSM when an input is not recognized (i.e. the input is not contained in the alphabet)?
In Sipser's Introduction to the Theory of Computation, the provided proof for the union operation being closed for regular languages has a step for the transition function that I find a bit lacking.
...
1
vote
1answer
52 views
Why does the Pumping Lemma Constraint |xy| ≤ p mean that y can't be 1 in the string 0p1p
I am trying to get my head around the Pumping Lemma to prove a language is non-regular.
I am reading the Sipser text book and he gives the following example.
Let B be the language $\{0^n 1^n | n \ge 0\...
-1
votes
2answers
57 views
DFA for $\{0^m1^n \mid m+n \text{ is even}\}$
How do I construct a DFA for the language $\{0^m1^n \mid m+n \text{ is even}\}$? The corresponding regular expression is
$(00)^*(11)^* + (00)^*0(11)^*1$.
1
vote
1answer
59 views
How to prove a language isn't necessarily regular? [duplicate]
Assuming we have a regular language $L$, how can we prove that $L'= \{ xz \mid \exists y : xyz \in L \text{ and } |x|=|y|=|z|\}$ isn't necessarily regular.
So far I can't come up with much for how to ...
1
vote
1answer
51 views
All prefixes with same length as their suffix is a regular language
Suppose $L$ is a regular language over $\Sigma$ and we want to show that $$\frac{1}{2}L = \{x \in \Sigma^* \mid \exists y \in \Sigma^* (xy\in L \wedge |x| = |y|)\}$$ is regular. I thought of taking ...
4
votes
0answers
39 views
Simultaneous reachability of NFA states
Suppose I have a $n$-state non-deterministic finite automaton $F$ over alphabet $\Sigma$. Let $S(x)$ be the set of states reachable from the starting state by consuming string $x$.
I am interested for ...
0
votes
0answers
21 views
What is the maximum number of initial states in NFA?
It is well understood that DFA has only one initial state. However, in NFA, multiple initial states are possible. As in NFA, it is equivalent to having a separate initial state with epsilon-...
1
vote
1answer
35 views
Intuition for irregular languages
I'm struggling in understanding how to recognize irregular languages.
I know what the meaning of irregular language but still find it hard to recognize.
Are there any tips to recognize better and to ...
0
votes
1answer
25 views
DFA containing substring to not containing substring by flipping acceptability of all states?
For example, $D_1 = \{ w | w$ does not contain baba as substring$\}$
For $D_1$, I would make $F_1 = \{q_4\}$.
As I tried to design $D_2$ as the complement of $D_1$ ...
