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,534
questions
5
votes
2answers
814 views
Automaton for telling whether a binary number is a multiple of 3
I am designing an automata which determines whether a binary number is divisible by 3:
$$ \{x \in \{0, 1\}^* \mid \text{$x$ represents a multiple of three in binary} \} $$
0
1
0F
0
1
1
2
0
2
1
2
...
-1
votes
0answers
7 views
Compare powers of PDM and FSM with Turing machine
Compare powers of PDM and FSM
with Turing machine.
6
votes
1answer
98 views
A Turing machine with each cell accessed at most $10$ times has an equivalent NFA
I am confused by the following claim:
Let $T$ be a (decider, single-tape) Turing machine with the property that for every input, every cell on its tape is accessed at most $10$ times. Then there is a ...
1
vote
1answer
17 views
DFA and a Partition of $\Sigma^*$
So I'm learning about Myhill-Nerode relations and as an introduction, the book describes possible partitions for $\Sigma^*$. As an example, given a language $L$, a partition of $\Sigma^*$ would be $\{...
0
votes
1answer
26 views
Proof no DPDA can accept Palindrome (need explanation for the attached proof)
The given proof for proving that no DPDA can be constructed to accept palindromes is unclear. There exists another similar question but it only explains the proof partially.
I understood how it aims ...
1
vote
1answer
49 views
Describing the language of this Automaton
I am trying to describe the above automaton in English. The pattern that I can see is that it accepts any input that starts with $1$ or $0$ with an exact one occurrence of $00$ and ends with 1 or 10. ...
1
vote
2answers
61 views
Is it accurate to contrast a Turing machine with finite automata by claiming the former is stateful and the latter is pure?
Recently, I was having a debate with a friend about what it would mean to create a machine that ZKSnarks (proves) itself. I tossed the word pure machine out there while describing what I hypothesized ...
-3
votes
0answers
23 views
Conversation from Mealey machine to moore machine
I want to understand the conversion from Mealey machine to moore machine with an example. How we derive the states.
1
vote
0answers
51 views
Is regex with lookaround still regular?
It is well known that "regex" with back-reference is not a regular expression anymore.
For instance, (.*)\1 matches any string repeated twice.
However, is ...
0
votes
1answer
55 views
How to create a DFA that accepts strings that are multiples of a number?
I particularly have a problem creating DFAs for multiples of larger numbers like 10, 11 ,12 etc. but I can create simple ones like 1, 2, 3 etc.
Even more so, I have a problem creating a minimized DFA ...
0
votes
0answers
16 views
Could I have used PL directly on this language instead of proving it the way I did? [duplicate]
In an exercise I'm trying to solve I have to say whether a language is regular or not. One of the languages is $L_1=\{0^i1^j \mid i,j \geq 1\text{ and } i\neq j\}$.
I have already solved this by ...
0
votes
1answer
25 views
Which z should I pick?
I'm currently trying to show that the language $L_2=\{0^n \text{ } | \text{ } n=2^k, k\geq 0\}$ is not regular by using the Pumping Lemma (at least I think it is not regular, because I couldn't find ...
1
vote
1answer
32 views
Problem with Understanding Pumping Lemma
I'm trying to solve this exercise that asks to determine whether a language is regular or not.
Following the flow of the course I figured that the exercise is a test for Pumping Lemma application. But ...
10
votes
1answer
484 views
What is the correct way to draw NFA of RE (a|b|c)?
We were assigned to draw NFA for regular expression a|b|c, so like any one I draw this
But my professor told me it is wrong, the correct way is
So, I checked it ...
1
vote
0answers
16 views
Design a two-tape deterministic Turing machine M that recognizes the language L3= {x#(0^k) #y : x, y ∈ {0, 1}* , x = y ∧ |x| = k}
I'm having a hard time trying to write a two tape Turing machine
I wanted to first think Oh all I'd have to do is scan from left-to-right till I find the strings that matches the accepted strings) ...
0
votes
1answer
24 views
What does c represent in Sipser's explanation of the modified post correspondence problem Introduction to the Theory of Computation book?
I'm supposed to perform actions corresponding to the different steps in Sipser's explanation of the Modified Post Correspondence Problem, but I'm not sure I understand the third step.
The part I'm ...
0
votes
1answer
14 views
What is the meaning of Sub_tm in this context?
Im working on a problem for a homework assignment in finite automata, but I'm having trouble conceptually grasping the problem in the first place.
Prove that the following is undecidable:
$SUB_{TM} = \...
6
votes
2answers
1k views
Proof that for 2n nodes of +1 and -1 position doesn't count
I'm having a hard time understanding how to solve this problem for my Computer Science 101 class.
On a circle there are $2n$ nodes. $n$ out of these hold -1 power and $n$ hold +1 power. Say we play a ...
1
vote
0answers
61 views
Is there a complexity measure on regular grammars connected to the descriptional complexity of the DFAs?
This question is directed at DFAs/NFAs and regular languages and regular grammars.
Define the "descriptional complexity" of a language as the size complexity of the family of DFAs that ...
1
vote
1answer
22 views
DFA minimazation (dead state)
I was trying to minimize given DFA:
a
b
-> 1
4
2
F 2
1
1
3
1
4
F 4
1
1
I've watched few videos about solving this problem and decided to use the equivalance method.
While doing it I've come ...
0
votes
1answer
30 views
How do we decide whether or not to accept $\epsilon$ in dfa?
Can I exclude $\epsilon$? Will that make a difference. This is really confusing me. It seems everything could contain $\epsilon$. Is there some way of thinking to realize this contains $\epsilon$ or ...
2
votes
0answers
21 views
How to build a minimal string matching DFA with limited memory?
I am working on finite state machine pruning, a problem that requires me to build finite state machines (in the manner of the Aho Corasic algorithm) to match an evolving input string against a set of ...
2
votes
1answer
32 views
Convert a dfa to rule for a asterisk case
Here is a simple but very common grammar rule case in EBNF format, the Statements is a none terminal symbol and Statement is ...
0
votes
1answer
56 views
How do I create a finite state automata for addition in ternary system?
I've been scratching my head with this one for a few hours now, but am feeling to stupid to comprehend how it is to be done. I can't understand the way even the state table should be built for this ...
1
vote
1answer
51 views
epsilon-NFA to DFA conversion - What will be the final states and do we need to create empty state in DFA?
Source of this question and problem:
https://www.javatpoint.com/automata-conversion-from-nfa-with-null-to-dfa
This is the question:
So in this figure there are my 1 confusion-:
Don't we need a empty ...
0
votes
2answers
51 views
When you convert epsilon NFA to NFA, how do you decide the final states of resultant NFA?
The question is-:
THIS is the transition table for NFA-:
Final result as shown in youtube video.
https://www.youtube.com/watch?v=GjLiXk0imi0&list=PLENQMW_c1dimRCKF3bjUqHaH8dvJkapSw&index=49
...
-2
votes
1answer
36 views
What does DFA that accepts at least 1 a or at least 1 b mean?
What are the language accepted by this DFA?
The truth table of OR-:
But I am unable to deduct what this dfa will accept?
Say-:
P=at least 1 a
Q=at least 1 b
So DFA should accept both ab. Or in ...
0
votes
1answer
33 views
Regular expression for set of all strings containing no 3 consecutive 0s?
The answer is
$1^*01^*01^*+1^*(0+00+\in)1^*$
If I had to rephrase my question, it would be how to approach regular expression problems? Is it all about practice?
How do I understand what the regular ...
1
vote
2answers
38 views
NFA has power to be in several states at once implies NFA has ability to guess about its input. How?
I agree that NFA has power to be in several states at once. It probably means that on same input, NFA can be on multiple states. But what I can't understand is how can we conclude from this that "...
0
votes
1answer
34 views
DFA for {w|w contains a substring of length at most 5 that has at least three 1's}
I have thought about this problem, but cannot come up with a convincing answer since I think this problem has too many states too consider. The accepting states can be length 5 substring and 3 1's, ...
0
votes
0answers
31 views
conversion of epsilon NFA to NFA
I was given below task:
Eliminate Epsilon-transitions in below automata
My solution:
Is it correct that stage 1 is actually one of the final stages?
How does it work in given example? We have ...
1
vote
1answer
34 views
conversion of NFA to DFA (omitted states)
I've been given following task:
Determine the following nondeterministic automaton (omit unreachable states, if they appear during construction)
My solution to this:
Would like to ask for a ...
0
votes
1answer
14 views
Problems with simulating NFA with DFA
I have this NFA:
I want to simulate it with a DFA, thus I have the states {1}, {2}, {3}, {1,2}, {1,3}, {2,3} and {1,2,3}. Usually I look at every state and find out in which state I could end up when ...
0
votes
1answer
46 views
Need help with constructing a DFA
I am trying to construct the DFA that accepts the following language
$$ L_2 := \left\{ w \in \{a,b\}^* \mid \#a(w) \text{ is divisible by } 3 \text{ and } \texttt{babbab} \text{is a substring of } w \...
1
vote
1answer
32 views
What is the difference between these 2 dfas for binary strings ending with 00?
The first one is from unreputed youtuber whereas second one is from reputed university called adiuni course of theory of computation.
Now I know what that second figure means, it means it also accepts ...
2
votes
1answer
51 views
Are Nondeterministic Finite Automata not allowed 'sink-states'?
By definition are Nondeterministic Finite Automata not allowed a 'sink-state' (non-accepting state we don't get out of)? I can see us having them for NFA but not necessary but do not see how they are ...
2
votes
1answer
124 views
How to verify-: A language over Σ is also a language over any alphabet that is a superset of Σ?
Context-:
A language over Σ need not include strings with all symbols of Σ Thus, a language over Σ is also a language over any alphabet that is a superset of Σ.
https://www.univ-orleans.fr/lifo/...
3
votes
4answers
172 views
Are there any programming languages that support state machines in their standard library?
State machines are a fundamental computer science concept and in many senarios they are the simplest way to implement a process or program. However, most programming languages don't support them ...
-1
votes
1answer
91 views
Design a DFA that accepts numbers whose sum of digits is $2 \mod 3$
Design a DFA that accepts language $$L = \left\{ x \in \{ 0, 1, 2 \} : \text{ sum of digits in } x \text{ is } 2 \mod 3 \right\}$$
How to make a DFA for this? I have no idea how to solve this dfa ...
-3
votes
1answer
52 views
Design a DFA that accepts language L={ x in (0,1)* | the third bit from x from its right end is 1}
this is very confusing question. I am having no idea to solve it, can you please guide me here?
0
votes
1answer
48 views
DFA for even number of 1's
My attempt at solution-:
Solution by a teacher-:
Both are giving same answer, is the one that I made correct?
-2
votes
2answers
76 views
Prove that the class of regular languages is closed under three operation
We define an operation three on strings as three(c1c2c3c4c5c6...) = c3c6... then the above-described definition is extended to languages. Prove that the class of regular languages is closed under this ...
0
votes
1answer
50 views
Prove the class of regular languages is closed or not closed under the operations below
Suppose $A$ and $B$ are both languages over $\Sigma=\{0,1\}$. We use $n_0(x)$ and $n_1(x)$ to represent the number of $0$s and $1$s in the string $x$ respectively. Consider the following two ...
0
votes
1answer
56 views
Size of minimal DFA
Assume a given NFA for a regular language with $n$ states. It is clear that determinizing it may result in an DFA with $\Omega(2^n)$ states. However, the minimization might decrease the number of ...
1
vote
2answers
44 views
What is the minimum pumping lemma length of $01^*0^*1$?
I've taken the following steps to prove that the minimum pumping length (PL) of the above language, $L= 01^*0^*1$:
Set a PL. I chose $p=2$
Choose a string from $L$ where $|w|\geq p$, I chose $w=011$. ...
0
votes
0answers
58 views
If $L$ is regular, is $L/w = \{x\mid wx\in L\}$ regular?
I'm trying to see if the language $L/w = \{x\mid wx\in L\}$ is regular given that $L$ itself is regular.
It seems to me that if $L=L(A)$ for the NFA $A = (Q, \Sigma, \delta, S, F)$, then the NFA $A'$ ...
2
votes
2answers
58 views
If L is regular so is the language of compressed doubles
Suppose L is a regular language over the alphabet $\Sigma$. I need to prove that
$$ L'=\{x_0\cdots x_n:x_0x_0x_1x_1\cdots x_nx_n\in L, \ \ x_i\in \Sigma\}$$
I thought I could take a DFA which computes ...
0
votes
2answers
165 views
Regularity of CFG and DCFL
I read that it is undecidable whether, given a CFG $G$, $L(G)$ is regular. And there exists no algorithm that, given a CFG $G$ such that $L(G)$ is regular, outputs a DFA that accepts $L(G)$.
My ...
0
votes
0answers
12 views
Need literature on First order logic definibility through Automata
Actually I am in search of some good literature on defining First order logic through Automata. It will be very helpful if someone can give me some links.
0
votes
0answers
75 views
My proof for equivalence of DFA and NFA
I came up with this proof for the following theorem:
If $L$ is a language produced by an nfa, then there exists a dfa $M$ where $L(M) = L$.
Is it correct? If it's not, what are the flaws of my proof,...
