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,486
questions
0
votes
0answers
22 views
DFA and RE find out the language. Please can you explain?
Find the regular expression describing following languages over alphabet {0, 1}*.
...
1
vote
1answer
86 views
What is the regular expression for the language, {w | w does not contain the substring 11}
{w | w does not contain the substring 11}
What I am thinking: $(0^* 1 0^* )^*$
Is anything wrong with my expression?
Thanks in advance for your help!
-1
votes
0answers
35 views
A formal proof of Arden's Theorem [duplicate]
I have been searching internet for a correct proof of Arden's Theorem and have searched some book also. Many proofs seem to be completely wrong, filled with fallacies and can't trust what is written ...
0
votes
2answers
31 views
Existence of infinite unique FSAs
It is reasonably simple to show that there are an infinite number of different finite state automata that can be constructed, but has it been proven if there is an infinite number of unique finite ...
1
vote
2answers
279 views
(How) Can I remove a word from a DFA?
As the title says, is it possible to remove a word from a DFA? One obvious way is to calculate the language without the word that I want to remove and then construct the DFA for the updated language. ...
-3
votes
1answer
34 views
I want to know the difference between DFA and FSA
Taking a class named Theory of Computation. Learned about Deterministic Finite Automata and just got introduced to Finite State Automata. I can't figure out the difference, are they just synonyms?
...
3
votes
1answer
35 views
Can a non deterministic finite automaton go into infinite loop?
Here is the exact same question but on deterministic finite automaton. The case for deterministic finite automaton is simple. For each state only one transition is possible for each input symbol and ...
0
votes
1answer
42 views
Simplifying the Language of this DFA
Above's the DFA in question (Sipser, Page 36). I have obtained the language of this DFA to be 0*1(1+00+01)*. But Sipser's textbook goes on to explain that the language of this DFA is (0+1)*1(00)*. But ...
0
votes
0answers
54 views
Regular language closed under homomorphism
I am trying to solve problems from the textbook 'Introduction to the Theory of Computation' by Micheal Sisper, 3rd edition.
I am attempting to show various properties of regular languages and their ...
2
votes
1answer
50 views
Implication of the Pumping lemma
I'm reading Hopcroft and Ullman's '79 edition of "Introduction to Automata theory, Languages, and Computation". In chapter 3, the authors say "The lemma[sic] does not state that every ...
-3
votes
0answers
38 views
How to minimise the DFA
I was going through some DFA minimisation questions. I got stuck here. Can someone help me how to minimise the DFA in the image?
1
vote
0answers
37 views
What if have a algorithm that could generate a NFA of 42 states of any binary string of 2^32 length?
For example, if we have a true algorithm that could generate any NFA of at most 42 states from any binary string of 2^32 length. So, this algorithm can not just recognize the string but just recreate ...
1
vote
1answer
30 views
Find a transducer that maps a given deterministic process to another
Let $S$ denote a deterministic process which generates a certain string, described through a Hidden Markov Model. More specifically, for a process with alphabet $\mathcal{A}$ and $n$ hidden states, ...
1
vote
2answers
58 views
Can a non-deterministic finite automaton die out before reading the entire string?
I am new to automata theory and have a problem that I want to solve. We have to design an NFA that starts with "ab". I have the solution and it is given by:
However, my problem is:
If the ...
2
votes
2answers
91 views
Why {${xww|x,w∈(a+b)^*}$} is regular but {${ww|w∈(a+b)^*}$} is not $? $
I read this site example 12 that {${xww|x,w∈(a+b)^*}$} the set of strings generated by language $L$ is {${ϵ,a,b,aa,ab,ba,bb,aaa,…}$} by taking always $w$ as $\epsilon$ and $x$∈$(a+b)^∗$. But my ...
0
votes
0answers
13 views
Cannot figure out what I am doing wrong with Mealy to Moore conversion
I've spent a lot of time on this and still cannot see what I am doing wrong, will appreciate any help. Below the source Mealy machine:
According to the solution, there should be two 1s in the ...
2
votes
0answers
43 views
Intuition for the reason this language which has equal number of 01 and 10 as substrings can be accepted using bounded finite states
Firstly I don't have CS or DFA/NFA background knowledge about their theorems or lemmas, so I don't understand some related questions' answers like here. However, I can easily intuitively understand a ...
0
votes
0answers
52 views
Are the regular expressions equivalent?
Is the following equivalence true?
$$(r_1^*r_2^*)^* = (r_1 + r_2)^*$$
I think these are equivalent since both the expressions generate the same strings: $\{\epsilon,r_1,r_2,\dots\}$ etc.
4
votes
2answers
217 views
Why are Regular sets not closed under infinite unions and intersections? [duplicate]
Why are Regular sets not closed under infinite unions and intersections, with my flawled reasoning I came to a conclusion that since infinite unions can have no relationship between strings of a ...
1
vote
0answers
26 views
Has anyone seen the following string classifier discussed?
The closes related question I have found for this is Find string patterns preferably in regex for string streams, but it has no answer and is also a little less constrained as my idea.
Given a set of ...
2
votes
1answer
27 views
Minimal state DFAs for a regular expression of length $n$
I know that given any regular expression, we can find always find a minimal DFA which accepts the language it describes. However, this process can take up to exponential time and space. I'm wondering ...
0
votes
1answer
32 views
Convert a PDA with transition for a state to itself to another PDA
Suppose we have PDA (same for DFA and Turing) that has a transition from a state to itself. Can we convert this PDA to another one without any transition like this?
EDIT (My thoughts):
I guess we can ...
0
votes
1answer
41 views
Prove $(aa^*bb^*)^*=ϵ+a(a+b)^*b$ using regex laws
I tried to prove this by starting at RHS:
$$ϵ+a(a+b)^*b = ϵ+a(a^*b^*)^*b$$
But I dont know how to convert $(a^*b^*)^*$ to something else that will be helpful.
Any ideas?
-1
votes
1answer
25 views
How can I implement a Deterministic finite automaton which accepts
Problem: implement a Deterministic finite automaton which accepts 01 ∪ (2∪10*2)*
∪ <- is union symbol
I have a lot of problem trying to implement that DFA, the union symbol always confuse me
Can ...
0
votes
1answer
445 views
Construct a DFA accepts set of all strings that begins with 01 and end with 11
I have drawn the DFA for language L1 containing strings starting with 01 and language L2 containing strings ending in 11. For the final DFA, I have concatenated both DFA's. The finals DFA does not ...
-2
votes
1answer
136 views
Construct a DFA which accepts all strings containing both 11 and 010 as substrings
I have drawn the DFA for language L1 containing 11 as substring and language L2 containing 010 as substring. But I don't know how to concatenate these two to get the final answer. Please help!
-3
votes
1answer
51 views
How can I convert from DFA in to regular grammar?
I have following information.
0 1
-> *q0 q0 q1
q1 q1 q2
q2 q2 q0
I have to convert this in to a regular grammar.
I wrote this:
...
-3
votes
1answer
35 views
How can I convert a Grammar to NFA?
Hello I have a task where I´m stucking at.
I have to convert a Grammar to NFA. I have these information:
G=(V,T,P,S) V={S}, T{0} and
S -> 0S
S -> 0
I can´t ...
3
votes
2answers
397 views
If regex describes FSAs, what string formats describe Turing machines?
(Topic summary under the line.)
Regex, at least the formal definition featuring only | and *, is used to describe words accepted by a given FSA, but it can be transformed into the corresponding state ...
2
votes
1answer
62 views
How to prove the same states are repeating in Synchronizable DFA?
I'm trying to prove the if $𝑀$ is a $𝑘$-state synchronizable DFA, then it has a synchronizing sequence of length at most $𝑘^3$. first I have to prove that if a string syncs two states, then its ...
0
votes
1answer
82 views
How to describe the language of an automaton in plain English?
How do I describe the following automaton in plain English?
The only thing that I can think about when explaining in plain English would be the states, alphabet, start, accepting state, but I think ...
3
votes
1answer
48 views
Efficient algorithm to find a rejecting input of an NFA
I cannot think of a PTIME algorithm to find a rejecting input of an NFA. While it is possible to efficiently find a rejecting input for a DFA, converting an NFA to DFA is too expensive.
The algorithm ...
0
votes
1answer
32 views
Question about an answer related to designing an ASM for a sequence detector
The question says:
Design a sequence detector that searches for a series of binary inputs to satisfy
the pattern 01[0*]1, where [0*] is any number of consecutive zeroes. The
output (Z) should become ...
2
votes
2answers
65 views
Prove the language $\{x \in \Sigma^* : \exists w \in \Sigma^* \ xww \in L \}$ for regular language $L$ is regular
Let $\Sigma=\{0,1\}$ and $L$ be a regular language. Prove that
$$Z(L) = \{x \in \Sigma^* : \exists w \in \Sigma^* \ xww \in L \}$$
is a regular language.
I tried to build a NFA based on the DFA that ...
-2
votes
2answers
30 views
Drawing transition diagram from transition table
I have a DFA transition table like
\begin{array}{cc|c|c}
& & 0 & 1 \\ \hline
\to & p & qs & q \\
* & q ...
1
vote
2answers
117 views
How is CLR(1) grammar more powerful than LALR(1) grammar
I am unable to understand how Canonical LR(1) grammar is more powerful than LookAhead LR(1). Both have lookahead symbols in their items and works almost similarly, so how can CLR(1) derive a larger ...
-2
votes
1answer
49 views
Finding the language generated by this grammar
I'm having problems with this. Can someone help me please.
Find the language generated by this grammar over the alphabet $\{0,1\}$:
$S\rightarrow BAB\mid CAB$
$BA \rightarrow BC$
$CA \rightarrow AAC$
...
1
vote
1answer
57 views
How to draw Turing machine for multiplying a number by 2 in base 10
I'm trying to design a turing machine that given a number in base 10 multiplies it by 2.
The problem seems trivial if the number is represented in binary so what I've thought is try to convert it from ...
1
vote
1answer
57 views
Proof that for every $k > 1$, there exists a language $A_k \subseteq \{0, 1\}^*$ s.t. a DFA accepting $A_k$ has $k$ states but no less
I am trying to prove that for every $k > 1$, there exists a language $A_k \subseteq \{0, 1\}^*$ such that a DFA accepting $A_k$ has $k$ states but no less.
I thought about proving this in two ways: ...
3
votes
1answer
102 views
NP completeness of deciding whether a set of examples, consisting of strings and states, has a corresponding DFA?
I'm working on a textbook problem, 7.36 in Sipser 3rd edition. It claims that if we are given an integer $N$ and set of pairs $(s_i, q_i)$, where $s_i$ are binary strings and $q_i$ are states (we are ...
1
vote
1answer
28 views
NFA designing for strings starting with $01$
The question was asked
Construct an NFA with set of all strings that start with $10$.
The solution provided to me is
But my question is what if the automaton receives an input $0$ at the starting? ...
1
vote
1answer
25 views
Possibility of using loops instead of traps
Draw DFA for the language of all strings starting with $a$ and ending with $b$.
Now what I have done is
Here I used q3 as a trap.
But could I do this instead?
I have not used trap in the 2nd ...
0
votes
1answer
40 views
Is it possible to create a NFA that accepts only n*"a" or n*"b" inputs?
I'd like to create a NFA that accepts only inputs like "aaaaa";"a";"bb";"bbb", but not like "aab";"aabaa".
Is the even possible? As far as I ...
4
votes
1answer
54 views
Maximal minimal DFA for some language of n-bit strings
Notation: $M$ is a DFA; $L(M)$ is the language accepted by $M$; $\min(M)$ is the minimal automaton equivalent to $M$ derived from a minimization algorithm such as the Hopcroft algorithm; and $|M|$ is ...
0
votes
0answers
24 views
How NFA decides how to break up a string?
If we have a language K, that word w=uv, accepts.
$K= \{{w \in \{a, b ,c\}^*: \ \vert u \vert_a \ \text{is not divisible by 3}}\}$. Can we land strings like aaaa ...
0
votes
0answers
34 views
Prove language is not Turing-recognizable using contradiction
Show that the language L = {<M>| M is a TM and does not accept <M>} is not Turing-recognizable.
Note: Prove by contradiction. No need for reduction.
This is the problem I am trying to ...
0
votes
1answer
36 views
DFA for language
I want to give a DFA for the language which contains the words X ∈ {0,1,2}* for which the number of 0's + number of 1's is even AND the number of 1's + the number of 2's is odd.
I tried many ...
1
vote
0answers
38 views
What is the connection between finite automata and logic (sequential calculus)?
Languages recognized by finite automata are exactly those definable
by sentences of the sequential calculus, and also exactly those
definable by rational expressions (also called regular expressions)
...
0
votes
0answers
27 views
Finite Automaton to Turing Machine Example
I cannot seem to find an example of an NFA and Turing Machine that both accept the same languages. I am trying to understand how to convert an NFA to its equivalent Turing Machine and I think a simple ...
-2
votes
1answer
43 views
Regular expression for binary representation of even numbers?
I need help writing the regular expression over the alphabet (0,1) represent the even numbers in base ten. So basically the regular expression would show represent an even number in binary. (also if ...
