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.

Filter by
Sorted by
Tagged with
-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$ ...

1
2 3 4 5
29