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,702
questions
0
votes
1
answer
26
views
Constructing product automaton with conjunctive conditions
The question was to construct a DFA which accepts the language $$\{ x \in \{0,1\}^* \mid x\text{ starts with a }0\text{ and has at most one }1\}$$
So I first constructed DFA for '$x$ starts with a $0$'...
- 105
3
votes
2
answers
1k
views
NFA: How does it function with empty-string moves?
How does the NFA function on $\epsilon$ input if there is only a single $\epsilon$ string in the language?
I understand that $L^* = \bigcup_{i=0}^\infty L^i$ where $L^0 = \{()\} = \{\epsilon\}$ and $L$...
- 175
3
votes
2
answers
309
views
How to build a deterministic finite automaton from a given one with a new definition for automaton language?
I was given a new definition for a language of an automaton.
A word is part of the automaton language if and only if the automaton finished on an accepting state and it was in an accepting state at ...
- 261
0
votes
0
answers
89
views
Description of an automaton
i'm a student and i've been searching the language description of this automaton.
The states are as follows: Q = {q1, q2, q3,q4}
The alphabet is as follows: Σ = {0,1}
The start state is q1
The ...
0
votes
1
answer
170
views
Construct a DFA with $\Sigma=\{0,1\}$ that accepts the language $\{ x \in \Sigma^* \mid x \notin L(0^*1^*) \}$
I am trying to construct a DFA with $\Sigma=\{0,1\}$ that accepts the language $\{ x \in \Sigma^* \mid x \notin \mathcal{L}(0^*1^*) \}$. To do this I first tried constructing a DFA that accepts $x \in ...
- 105
0
votes
2
answers
250
views
Constructing a DFA with $\Sigma=\{0,1\}$ that accepts $L= (0\vert10)^*$
I am trying to construct a DFA with $\Sigma = \{0,1\}$ that accepts $L = (0\mid10)^*$, below is my attempt, but I'm a bit stuck.
The quiz marked it wrong since there's no transition from $q_1$ under $...
- 105
1
vote
1
answer
237
views
Prove that there is no $DFA$ with less than $2^n$ states that accepts $L_n =\{w\in\Sigma^*_n\ |\ \exists\sigma\in\Sigma_n\ :\ ⋕_\sigma(w)=0\}$
I've faced this question in my homework and I couldn't provide elegant proof for it.
We're given $\Sigma_n=\{1,\dots,n\}$ and a language: $$L_n =\{w\in\Sigma^*_n\ |\ \exists\sigma\in\Sigma_n\ :\ ⋕_\...
- 453
1
vote
0
answers
18
views
Produce a CFG for $\{a^ib^j \mid i<j\}$ [duplicate]
How do I go about producing the context-free grammar for something like $\{a^i b^j \mid i<j\}$?
If it was $i=j$, then it's simple. But for something like this, is there a process to achieve it, or ...
- 19
0
votes
0
answers
180
views
How to convert a null state transition in nfa to dfa
i am looking to convert regular expression 0* 1* to deterministic finite automaton (DFA)
I have tried creating the NFA for the regular expression as given in the above image,
From the regular ...
- 1
1
vote
1
answer
103
views
DFA for $a+b=c$, where $a,b,c$ are input in parallel
I've faced this question in my homework, it's a bonus question so it's harder than I could do now with my current knowledge, so if anyone could help I'll be thankful.
We're given $\Sigma=\{0,1\}^3$. ...
- 453
0
votes
0
answers
50
views
Languages with number of $a$'s a perfect square
Is there any finite automata ((N/D)FA, NPDA, DPDA, or any variation of a Turring Machine) that can accept the following language:
$\{s \text { is a string over } \{a,b\} \text { such that the number ...
- 141
1
vote
0
answers
30
views
Is there an algorithm for generating non comparable boolean vectors?
First some context:
A Boolean Network of $n$ components is a function $f$ from the set $\{0,1\}^n$ (set of vectors of $n$ components whose values are 0 or 1) to itself.
The dynamical behavior of a ...
- 111
-1
votes
1
answer
44
views
What is the language that this DFA accepts?
I've faced this question in my homework, I tried to solve it but I couldn't.
We're given a DFA:
Every time I tried to define the language, I found a word that the DFA accepts but the language I ...
- 453
2
votes
0
answers
62
views
Translating weighted regular expressions with the complement operator to weighted deterministic automata
I want to implement regexp search via translation to deterministic automata, as a toy project.
TLDR: how to combine the extended regular expressions with the weighted regular expressions, with the ...
- 181
-2
votes
1
answer
167
views
Is this language regular or non-regular : {ww | w ∈ {a,b}* } ∩ {a}*
I think it's a regular language but I can't find a DFA or a regular expression. Would anyone know how to help me?
- 11
0
votes
1
answer
83
views
Intersection of Infinite Regular Language with CFL
Intersection of any finite regular language with anything( CFL or not CFL) will be finite but what about intersection of infinite regular language with CFL or not CFL. Does the resultant will be ...
1
vote
1
answer
522
views
Regular expression of binary strings not containing $1011$ or $1101$ as substring
I tried to solve by explicitly writing strings of length $2$, $3$ and $4$ (other than $1011$ and $1101$), but it creates a lengthy regular expression. Can someone suggests underlying pattern that ...
- 111
0
votes
0
answers
68
views
what's the differenece between finite state automaton and finite state automata
Upon googling all I get is the definition of finite-state automaton but what's the difference between it and finite-state automata or are they the same
- 101
0
votes
0
answers
39
views
What is the standard definition of recursive automata (or state machines)?
I found this paper:
https://courses.engr.illinois.edu/cs373/fa2009/recaut.pdf
But it looks like recursion is done along an edge. I would have thought you have state machines nested inside nodes. ...
- 473
4
votes
2
answers
1k
views
Prove that every substring closed language L ⊆ {0, 1}* is regular
For $x,y \in \{0,1\}^*$ a language $L ⊆ \{0, 1\}^*$ is called substring closed, if $y \in L$ and $x \preceq y$ ($x$ substring of $y$) implies $x \in L$.
I want to prove that every substring closed ...
- 197
0
votes
2
answers
327
views
For a regular language L, the language of all words such that no prefix of them are in L is also regular
Prove that for every regular language $L$, the following language is regular:
$L_{pf}=$ $\{x \in L | $ no proper prefix of $x$ is in $L\}$
How should I prove this?
I understood that $L_{pf}$ is just ...
- 197
0
votes
1
answer
65
views
What could be possible NFA for the RegEx "a?"
I am trying to use the Thompson's method to draw an NFA for a RegEx given by: $(a+b|c?)c$
I am wondering if I should deconstruct the RegEx as -
Concatenation of $a+$, $(b|c?)$ together with $c$ OR
...
0
votes
3
answers
677
views
Understanding proof that no DFA can recognize L with fewer than 2^k states
Let Σ = {a, b} and L = {ww | w ∈ Σ∗ and w is of length k}. Show that for each k, no DFA can recognize L with fewer than 2^k states.
What I understand is that we prove this by contradiction. Assume ...
1
vote
0
answers
50
views
Finite-state transducer to accept $i$'th word of DFA
If I have a DFA $D$ that accepts some regular language $L$, is it possible to construct some finite-state transducer $T$ that takes in an index $i$, and puts out the $i$'th word in $L$, ordered ...
- 368
-1
votes
2
answers
366
views
Convert ((ba ∪ ab)∗ ∪ b)* to NFA
How do I simplify this $((ba \cup ab)^∗ \cup b)^*$? I can draw the NFA for the '$ba$', '$ab$' and '$b$' term but when it comes to linking the '$ba \cup ab$' to the '$)^∗ \cup b)^*$' i am unsure how ...
- 1
0
votes
0
answers
24
views
How ot prove a language is regular using L′ = {ab(^i)c)^i) | i ≥ 0 [duplicate]
I have the following language
L = {a(^i)b(^j)c(^k) | i, j, k ≥ 0, and, if i = 1 then j = k} .
How do I use the fact that L′ = {ab(^i)c)^i) | i ≥ 0 to prove that is it not regular?
I am given a hint ...
- 1
1
vote
1
answer
41
views
How can I know if more non-determinism can be used in an NFA?
I have to give the transition diagram of an NFA accepting all strings that are not empty and start and end with the same symbol, I should also use non-determinism as much as possible (language is {0,1}...
- 123
-1
votes
1
answer
216
views
DFA Automaton with at least two 1s every four digits
How can I create a DFA automaton that will have every four digits (if they exist) at least two 1s for strings of languages with alphabet {0,1}?
The expression at least two 1s seems easier than the ...
- 133
1
vote
1
answer
87
views
How does $xy^0z = λ$ not contradict $y \ne λ$ in the pumping lemma?
I have just started out theory of automata in my university and we are studying the pumping lemma.
From what I have understood, the lemma states that $y \neq \lambda$ (where $\lambda$ is the empty ...
- 25
0
votes
0
answers
98
views
How do I prove a language is not regular using L′ = {a b^i c^i | i ≥ 0}?
I have just started my masters without any substantial experience in programming and I am struggling to understand certain concepts.
I have been given the following language $$L = \{a^i b^j c^k \mid i,...
- 1
7
votes
2
answers
1k
views
Automaton for telling whether a binary number is a multiple of 3
I am designing an automaton 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
...
user145450
7
votes
1
answer
253
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 ...
- 171
1
vote
1
answer
32
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 $\{...
- 29
0
votes
1
answer
86
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
1
vote
1
answer
161
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. ...
- 111
1
vote
2
answers
152
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 ...
- 133
4
votes
1
answer
167
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 ...
- 141
0
votes
1
answer
525
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 ...
- 35
1
vote
2
answers
46
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 ...
- 225
1
vote
1
answer
43
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 ...
- 225
10
votes
1
answer
873
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 ...
- 215
1
vote
0
answers
111
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) ...
- 11
0
votes
1
answer
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 ...
- 23
0
votes
1
answer
41
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} = \...
- 23
6
votes
2
answers
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 ...
- 225
1
vote
1
answer
44
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 ...
- 31
0
votes
1
answer
265
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 ...
- 37
2
votes
0
answers
73
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 ...
- 866
2
votes
1
answer
129
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 ...
- 19
0
votes
1
answer
142
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 ...
