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
vote
1answer
163 views
Define a DFA that accepts all even length binary strings that don't contain the substring “111”?
I think I have worked out a DFA that doesn't accept the substring "111," but I don't know how to account for accepting even length strings. Here is what I have so far. Any help would be greatly ...
-1
votes
0answers
16 views
Given a State machine M, Express these in LTL
I got this question in my exam. Can someone explain, what will be the correct answer for this. Thanks in advance.
Given the language of the question, will you consider this answer correct?
(where i ...
0
votes
0answers
13 views
Extended regular expression and intersection of languages of DFAs
I'm new with extended regular expression and I want to know if there are connections with the intersection non-emptiness problem of languages of DFAs.
I would like to see some research articles on ...
5
votes
2answers
102 views
Why do DFAs with a single final state have less power?
I came across this question in a test and I had to answer whether it is true or false.
DFA with single final state has the same powers as DFA with more than one final state.
I was confused by what ...
2
votes
2answers
63 views
Show that if L is regular, then third(L) is also regular. Hint: Construct an ϵ-NFA from the DFA for L
I'm having trouble with proving the following, and my attempt and confusion is mentioned further below.
PROBLEM STATEMENT:
For a string $w = a_1 a_2 a_3 a_4 a_5 a_6 a_7 \dots$, define $third(w) = ...
0
votes
0answers
8 views
converting automaton into dfa and finding the language it accepts [closed]
i am trying to practice converting into minimal FDA and finding the language it supports. could you please check if i did correctly and correct me if i've done any errors?
basic digraph:
after ...
1
vote
1answer
20 views
is it possible to know if a language is regular if its equivalence classes are finite?
i have a theoretical questions, and was wondering if you could help me with it so i could understand the material better.
1)suppose we have some language L over $\Sigma$, can we know if L is regular ...
2
votes
1answer
33 views
Subset of a regular language, for each of whose words there exists an element with the same number of 1s in the other regular language
For regular languages $A,B\subseteq\{0,1\}^*$, is
$$L_2 = \{x \in A \mid \exists y \in B : |x|_1 =|y|_1 \}$$
regular, where $|x|_1$ means the number of appearances of 1 in the word $x$?
i need to ...
1
vote
1answer
24 views
DFA that accepts strings with last character being repeated at least 1 time before
I'm trying to design a DFA in a 4 digit language, for example L(a,b,c,d) or L(1,2,3,4) that accepts strings with the last character being already repeated before.
Everyway im trying, i get so many ...
0
votes
1answer
73 views
Is this concatenation of two FA done right?
$r_3=r_1r_2=(a^*b)^*(a+ba)^*bb(a+b)^*$ comes out to be $r_3=r_2=(a+ba)^*bb(a+b)^*$ when i generate the resultant FA and its regex after concatenation i.e. it doesn't include $r_1$
Details:
Consider ...
-1
votes
1answer
20 views
Is it possible to create a regular language from an non regular language? (details inside)
I am wondering, is it is possible to create a regular language from a non regular language if we add or remove finite number of words from it?
say L is irregular, if we add or remove finite number of ...
1
vote
1answer
34 views
Exactly what is the difference between Finite Automata and Transition Graphs?
I haven't found a good enough answer by googling. Here's what i know:
TG's can have more than one initial state
In TG's, Edges/transitions can be labelled with strings
In TG's, it is not necessary to ...
2
votes
2answers
277 views
Language of all strings that has exactly 1 triple b
I am new to automata and learning to make regular expression for languages. But I have been stuck on this one.
Suppose we have a language L, Language of all strings that has exactly 1 triple “b” ...
1
vote
1answer
14 views
Number of states in DFA equivalent to given NFA
Let's say there is a NFA with $n$ states with an alphabet consisting of $x$ symbols. I convert it to an equivalent DFA. Can I say that the number of states in the equivalent DFA is $x^n$?
1
vote
1answer
20 views
Determining initial and final states from FA diagram
I am new to automata. And learning to find concatenation of two FAs. But this one has confused me
I know how to do concatenation but I am confused that in FA 1, what does x1 means? Is it mean final ...
1
vote
1answer
19 views
Trouble understanding this proof about the minimum number of states of a deterministic finite automaton
So I was browsing online looking for the general structure to proving a DFA has a minimum of $n$ states for some $n$ and most of them use contradiction. However, I'm having a hard time understanding ...
0
votes
1answer
46 views
regex - difference between $\Lambda+(a+b)^*b$ and $(b+aa^*b)^*$
$r_1=\Lambda+(a+b)^*b$
$r_2=(b+aa^*b)^*$
$r_3=b+\$+aa^*b+(b+\$+aa^*b)(b+aa^*b)^*(b+\$+aa^*b)$
For this FA, which i think of as accepting "$\Lambda$ or anything ending in $b$", i came up with $r_1$, ...
1
vote
1answer
46 views
Relationship between Deterministic Finite Automata languages
What this "⊃" superset means? What do I need to prove here. Can someone, please, explain in English?
Do I need to do a cross product?
Plus, in textbooks and online I only see "∩" "∪" these kinda ...
0
votes
0answers
13 views
Regex engine: A polynomial algorithm for backreferences?
During my search for a way to integrate efficiently backreferences (using backtracking) into a text-directed regex engine, I found a paper entitled Extending finite automata to efficiently match Perl-...
1
vote
0answers
25 views
Extending Thompson's NFA algorithm with backreferences
I'm looking for an algorithm as efficient as possible for a regex engine that supports submatch tracking (a.k.a capturing parentheses) and backreferences. What I mean by as efficient as possible is ...
1
vote
1answer
14 views
Automaton without variables and guards for queueing system
Disclaimer: Assignment question.
I am trying to solve the below question, the condition is not to use guards and variables. Is it at all possible to do this?
My approach was to have 4 separate ...
0
votes
0answers
35 views
What is the difference between Transition Graph and Generalized Transition Graph in finite automata?
These are graphs in finite automata. What is the difference between them and which relaxations do they provide?
0
votes
1answer
77 views
How can I make automaton that has given language? [closed]
I am trying to solve above question, below is the automaton I came up with:
Is there any ways to define automaton without having marked states?
0
votes
0answers
25 views
First part of L=L(A) proof (L(A)⊆L) proves that “δ̂(p,w)=p⇒w has even number of 1s,” so does second part (L⊆L(A))'s use depend on first part's use?
For this proof problem ( https://www.docdroid.net/IcdzSBt/theproblemanditssolution.pdf ), which includes its solution, does the "δ̂(p, w) = p ⇒ w has even number of 1's" from the second part (L ⊆ L(A))...
1
vote
2answers
32 views
What to do with empty set during NFA to DFA conversion?
I am currently converting this NFA to a DFA
I have come up with the following DFA:
...
2
votes
1answer
55 views
Why does the concatenation operation imply the empty string?
I'm a noob reading Michael Sipser's Introduction to the Theory of Computation, and I'm at a part where he's demonstrating how to construct finite automata that accept languages described by regular ...
5
votes
3answers
194 views
DFA that rejects $a^{23}$ but accepts $\{a^i|i\geq 24\}$
Construct a DFA $M$ with $\Sigma = \{a\}$ and max. 11 states so that $a^{23}\not\in L(M)$ but $\{a^i|i\geq 24\}\subset L(M)$.
I don't see how it is possible? Because it's a DFA and the alphabet only ...
1
vote
1answer
49 views
FSA for $(ab)^*(cb^n)^*$ [closed]
How can I prove that this language is regular, possibly by making a finite automata for this: $(ab)^*(cb^n)^*$, where $n\ge1$?
An automaton can easily be drawn for the part $(ab)^*$, but the part $(...
0
votes
0answers
14 views
Example of a language with linear NFA, but exponential DFA [duplicate]
So I read that regex engines use NFAs instead of DFA because f size blowup for dfas. I want to get an example of a language for which the minimum DFA has an exponential number of states but it,s NFA ...
1
vote
1answer
64 views
Context Free Grammer and PDA (Palindrome but without characters repeating in a row)
So this a question from my book and I have to make CFG of this language but I am confused what does it mean when it says
"L contains palindromes that don’t ever have the same character occur twice ...
-1
votes
0answers
22 views
Build a DFA/NFA for a language
Given a regular language $L$ with the alphabet $\Sigma$, I need to prove that the following language is regular by building a finite automata. (NFA/DFA)
$L'=\{xy\in\Sigma^* : xy\in L \text{ and } x\...
3
votes
1answer
45 views
Do multiple transitions over the input give finite state machines more power?
In the common model of FSA, the automaton reads the input string once, moving from one state to another after reading each letter in the input string. Epsilon transitions allow moving from one state ...
0
votes
0answers
26 views
Given a regular language L and only given an NFA that accepts it , is this enough to say that the complement of L is also regular?
"Given a regular language L and only given an NFA that accepts it then L'(the complement) is also regular"
Is this good enough proof to say that the complement is regular?
I keep being told this ...
1
vote
1answer
34 views
Proving that L is not regular by showing that $\equiv_L$ has infinite index
Proving that L is not regular by showing that $\equiv_L$ has infinite index.
$\Sigma$ = {a}, L = {$a^{3^n} : n \geq$ 0}
My ideas:
theorem of Myhill-Nerode: L $\in$REG $\Leftrightarrow$ $\equiv_L$ has ...
1
vote
2answers
199 views
Minimizing DFA - Dead state elimination
Following is a Question from a competitive exam, it is given that the solution is A but I don’t know why the dead state 4 is not eliminated.Dead states like 4 which has transitions only to itself, ...
-1
votes
1answer
14 views
Show that $R^{+} \equiv R \leftrightarrow L(RR) \subset L(R)$
Show that $R^{+} \equiv R \leftrightarrow L(RR) \subset L(R)$
sigma is any alphabet. R is a regular expression.
How can L(RR) even be a subset or equal to L(R)?
0
votes
2answers
39 views
Formal algorithm to test whether two given regular expressions define equal/identical or unequal languages
I'm trying to create a formal algorithm in order to determine whether
two given regular expressions $a$, $a'$ define identical/equal or
unequal languages and if those languages are subsets of each ...
2
votes
2answers
64 views
Prove regular languages are closed under $f(n) = 2^n$ and $ f(n) = n^2$
Suppose $ R $ is a regular language, let $ f(R) = \{ w | $ $ \exists x \text{ such that } |x| = f(|w|) \land wx \in R\}$, prove that $ f(R) $ is regular for $ f(n) = 2^n $ and for $ f(n) = n^2$. I've ...
1
vote
1answer
36 views
The reverse DFA is not working as expected
Assume a regular language contains all the strings that are ended with "01". We can draw the following DFA for it:
And I reversed the DFA according to this answer (designing a DFA and the reverse of ...
0
votes
0answers
22 views
For every nondeterministic finite state automata that has self-loop(s), there exists an equiv- alent nfa that does not have any self-loop [duplicate]
For every nondeterministic finite state automata that has self-loop(s), there exists an equiv-
alent nfa that does not have any self-loop
How can I prove this
Please suggest idea
Thank you
1
vote
2answers
711 views
Loopless NFA equivalent in strength to NFA
For every nondeterministic finite state automata (NFA) that has self-loop(s), there exists an equivalent NFA that does not have any self-loop.
How do I prove this?
1
vote
1answer
32 views
Proving the equivalence of two definitions of NFA acceptance
Recall that an NFA $N = (Q,\Sigma,\delta,S,F)$ accepts $w=w_1w_2\ldots w_n$, where $w_i \in \Sigma$, if one of the following holds:
(a) $\hat\delta(S,w) \cap F \neq \emptyset$, where $\hat\delta\...
2
votes
1answer
33 views
What is the algorithm for a decider to get the language accepted by a DFA?
I am trying to understand the larger problem of the decidability of the equality of two DFAs. I understand that this problem can be solved using minimizing DFAs, but my textbook states this can be ...
0
votes
0answers
30 views
DFA that accepts those words that a's or b's aren't divisible by 3
I'm have to draw DFA over alphabet $\{a,b\}$, which accepts words where ${a's}$ amount or ${b's}$ amount is not divisible by 3. I don't know how should I start and find out how many states I need.
I ...
2
votes
1answer
1k views
Can someone explain this conclusion for Finite State Machines?
PS It isn't a homework problem..
(But the results seems to be working for me when I checked manually a couple of values of m and n)
Let's say I have two FSM's(calling them A and B)
A is the the ...
0
votes
2answers
55 views
Does the distributive property apply to regular expressions?
Let $(Q,\Sigma,\delta, q_0, F)$ be a finite automaton, does
$$
(q_1a+q_2b)c=q_1ac+q_2bc
$$
hold for any $q_1,q_2\in Q$ and $a,b,c\in \Sigma$?
Here $Sa=\{\delta(q, a)\mid q\in S\}$ and $qa=\{q\}a$ ...
3
votes
2answers
51 views
DFA that accepts any integer $n$ such that $n \bmod 7 =1$
It seems impossible for me to find a pattern for integers $n$ such that $$n \equiv 1 \quad(\bmod 7)$$ in order to construct this DFA.
Is there smart way to do it without a machine which has memory ...
-1
votes
1answer
65 views
Can there exist two minimal dfa for same regular language?
As said the answer is pretty simple "no", but that is not what i encountered. Here is the summary : i took a regular language , produced two ways of accepting same language (the ways in my ...
1
vote
2answers
35 views
Is every language over any alphabets is accepted by automata?
The answer is no to what i have learned but i am finding difficulties to absorb it reason being . We say for every language we have a grammar as language without grammar makes no sense even in general ...
0
votes
0answers
44 views
NFA which accepts any $n$ such that $n \bmod 5=0$
I took into account that an integer can't start with a $0$ and that a $0$ could be present somewhere in the middle. Is the below NFA sketch the simplest possible?
