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
-3
votes
0answers
21 views

Use pumping lemma (non regular language) to solve

{0^m 1^n 0^m | m,n >=0} vv^R :v: {a,b}*
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} = \{...

1
2 3 4 5
28