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,399
questions
-3
votes
0answers
21 views
1
vote
1answer
30 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
14 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
40 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
0answers
35 views
Minimization of dfa condition [closed]
I am learning about minimization of dfa using partition method. In which we need to find 0 , 1 , 2 ,.... equivalence. I am just curious that what are the various necessary and sufficient condition ...
1
vote
0answers
14 views
Language of all words of the form $xwwy$, where $x,w,y \neq \emptyset$ [duplicate]
I have the following question:
Determine whether the following language is regular or not, and prove it:
$$L = \{xwwy \mid w,x,y ∈ Σ^*,w,x,y \neq ε\}. $$
My idea was that any string with at least 1 ...
0
votes
1answer
35 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
18 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
24 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
votes
0answers
12 views
Constructing a deterministic Turing machine
How does a DTM that starts with the configuration q00110010110 and end with the configuration ⊔p0000011111⊔ What would be the steps necessary to achieve these sequencing of 0’s and 1’s
1
vote
1answer
20 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.
...
-6
votes
0answers
28 views
Modify DFA/NFA that accepts Language
(a) Make a DFA that accepts all strings that start with ‘ab’, and end with ‘aa’.
1
vote
1answer
48 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
51 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
49 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
36 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
34 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
19 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
28 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
18 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
vote
1answer
25 views
All strings in which every substring 000 appears after every 1
I found this given problem as follows:
Write a regular expression where all strings in which every substring 000 appears after every 1.
Now, I also found the answer from Illinois university study ...
0
votes
0answers
35 views
halting problem vs watchdog
I have a theory that all finite state machines can be monitored by a second turing machine with infinite tape to determine if the state of the first machine was repeated thus reaching the conclusion ...
0
votes
0answers
25 views
Finite automaton for $\{0^{2n} : n \ge 0 \} \cup \{(100)^m : m \ge 0\}$ [duplicate]
I have to construct an FA for the following language:
$$
\{ w_1,w_2 \in \{a,b\}^* \mid w_1 = 0^{2n}, w_2 = (100)^m, \text{ for some } n,m \in \mathbb{N} \}.
$$
Does anyone here have any experience ...
1
vote
1answer
25 views
Confusion in understanding a DFA question
I am new to DFA and I am trying to understand the following question.
The alphabet is Σ = {0, 1}
Construct DFA for L = {0^n: n is either a multiple of 3 or a multiple of 5 }
Question
The above ...
0
votes
3answers
64 views
(Finite Automata) Why the following is a NFA?
The first one seems like a DFA. Could someone explain why this is a NFA?
3
votes
3answers
79 views
Minimal DFA for $1\Sigma^*0$
What is the minimum number of states required in any DFA to accept the regular language $L$ over $\Sigma=\{0,1\}$ which accepts those strings that start with 1 and end with 0?
6
votes
1answer
51 views
Determine the number of reachable states in a subset construction?
Is there a polynomial time algorithm to determine the number of reachable states in the subset construction of a NFA to a DFA without having to construct the entire DFA?
1
vote
1answer
38 views
Regular Languages and Separating Suffixes
Preparing for the next semester, I wanted to give the following as a homework question, yet after a few attempts, I failed to solve it.
Given a language $L\subseteq \Sigma^*$ and two words $x,y\in \...
2
votes
1answer
67 views
Conversion of $\epsilon$-NFA to a DFA
So, I was watching a video about the conversion of $\epsilon$-NFA to a DFA. In the resulted DFA, she didn't write the state 4 in any successor set of the sets containing the state 3, and her ...
0
votes
1answer
61 views
Conversion of RE to NFA
I've a question regarding this diagram. I'm thinking of adding a new state between q5 and q6 that accepts a lambda value but I'm not quite sure or this diagram is correct?
And in what situation we add ...
4
votes
1answer
44 views
Is there a method to generate the complement of a context-free grammar?
Given the languages $L_0 = {w \in \{0,1\}^*}$ such that $w$ is a palindrome and $L_1 = {w \in \{0,1\}^*}$ such that $w$ is not a palindrome, meaning $L_1$ is the complement of $L_0$, we want to find ...
4
votes
2answers
817 views
Why is this automaton considered DFA?
So I was watching this video https://www.youtube.com/watch?v=ZjjAbFxjxLQ and the guy was explaining why the top automaton is NFA (because the initial state doesn't know what to do if the input string ...
0
votes
1answer
91 views
What does 'Describe the language of this automaton' mean?
I've been asked to do this as part of an assignment. Here is the automaton:
I understood it as describing in terms of the 5 tuples so I wrote:
The states are as follows: Q = {A, B, C}
The alphabet ...
2
votes
1answer
90 views
Language Containment of Automata
If we are given an NFA and a DFA, can we determine if there exists a string accepted by the NFA and rejected by the DFA and vice-versa. What complexity class would these problems fall into?
0
votes
0answers
64 views
Possibly empty string in a DFA
I am trying to construct a DFA with this language L - all strings consisting of 0’s followed by a (possibly empty) string of 1’s followed by a (possibly empty) string of 0’s. I made the start state ...
2
votes
1answer
55 views
Minimal DFA accepting strings whose length is divisible by $x$ or $y$
Consider the language of all strings whose length is divisible by either $x$ or $y$, where $x,y \geq 1$.
After trying various values of $x$ and $y$, I noticed made the following observation:
If one ...
2
votes
0answers
23 views
closure property violated by palindrome language
It is well established that palindrome language is non-regular. The one way to prove it is by means of pumping lemma. The other way is violating the closure properties of regular language. The ...
2
votes
1answer
35 views
Why can PDAs have infinite stack but FSMs cannot have infinite state?
A Finite State Machine cannot accept the language
$$L = \{ 0^n1^n \mid n > 0 \} $$
because it will require infinite amount of memory to remember the number of zeros. But a Push Down Automaton can ...
4
votes
1answer
126 views
Kleene's Theorem and TMs
I wanted to know that based on Kleene's theorem (a language is regular iff some FSA recognizes it), does every regex have a TM (Turing machine) that halts on exactly the same language?
Is this ...
0
votes
0answers
21 views
PDA Explanation
{a^2i.b^3i | i ≥ 0 }
How would I draw this? I just started learning about pda's and I'm not sure where to start. I've looked at youtube videos explaining pda's but I'm still not understanding how to ...
0
votes
1answer
39 views
Myhill-Nerode classes for a Language $L_k = \{x1y | x \in \{0, 1\}^*, y \in \{0, 1\}^{k-1}\}$
This problem is from an exercise sheet so it would be nice if you could guide me to the solution.
The problem:
For $ k \in \mathbb{N}\setminus\{0\}$ let
$$L_k = \{x1y | x \in \{0, 1\}^*, y \in \{0, 1\}...
0
votes
2answers
67 views
Determine if the language of words with same number of 1's and 2's is context-free or not
$$L_2=\{w \in \{0,1,2\}^* : \text{$w$ has the same number of $1$'s and $2$'s}\}$$
I have tried creating PDA to determine if this was context-free or not. It seems like it would be because whenever a 1 ...
0
votes
0answers
43 views
Draw a CFG (context-free-grammar) that starts and ends with the same symbol yet has odd number of 1's
I figured out that the CFG that starts and ends with the same symbol in alphabet $\Sigma=\{0,1\}$ will be :
S -> 0A0|1A1|0|1|
A -> 0A|1A|𝜖
How can i interpret the odd number of 1's also?
0
votes
1answer
77 views
Turing machine state transition diagram vs finite state machine state transition diagram
If you were given a state transition diagram could you tell, just by looking at the diagram, if the diagram represented a DTM or a DFA (especially if it was unlabeled, just a directed graph)? Would ...
0
votes
1answer
31 views
Create an Finite Deterministic Automata for a regular expression
I want to create a finite state machine that accepts the following language:
$$
L=\{w\in\{a,b\}^* | w \text{ contains abb but not on the first position}\}
$$
So I began by writing a regular expression ...
0
votes
1answer
27 views
How do i prove this language is regular? [duplicate]
I have this language {0+1+0+} and i need to prove it is regular,i had the idea to use the closure properties but i can find any regular languages to unify perhaps.Any ideas?
1
vote
1answer
582 views
What does it mean for a grammar to be LR(0)?
I am unsure what it means for a grammar to be $X$. More specifically, what it means for a grammar to be LR(0).
For part of an assignment I had to form the DFA for a grammar, which I had no issues with....
0
votes
1answer
40 views
Converting Moore to Mealy When first Node has Output
This is a homework question, which I am able to do, except my teacher failed to mention what to do when the very first node has a 1 output. I've looked through online examples, and I'm sure this has a ...
2
votes
1answer
52 views
How do you create a sentential form in a given grammar?
I am given the following grammar:
$$S ::= aBS| abT |a$$ $$T::= d | dT$$$$B ::= da | ϵ | S$$
I need to decide whether $aBaabda$ can be produced in the given grammar.
I am unsure how the grammar can ...
1
vote
1answer
25 views
Can CFGs generate all languages? Are they (PDAs) finite or infinite state automata?
I was looking for the limitations of a CFG. I think there is some limitation given there are only finitely many states of a PDA (or non-terminals in a CFG).
I suspect that languages like $\text{L} = \{...
