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,164
questions
-1
votes
0answers
27 views
Draw an NFA over {0,1}
if I want to design a NFA (that's NOT A DFA) that accepts the set of all strings that do not contain the substring 1010, is this correct? because I can just accept 1010 by capturing it in the starting ...
-1
votes
1answer
41 views
Constructing a DFA of strings that are in A but not in B
I am tasked with creating a DFA for the regular language L = A/B, which are the strings that are in A but not in B. The alphabet is Σ = {a,b,c}
I am not really sure where to even start with this one, ...
0
votes
0answers
39 views
How do I convert the regular expression to a state digram?
I need to code an automaton that is equivalent to this expression:
('+'|'-'| )(D+ | D+ '.' D∗ | D* '.' D+)
where ...
1
vote
1answer
52 views
Let M be an $\epsilon$-NFA and let $S\subseteq Q$. Prove $\epsilon (S) = \epsilon (\epsilon (S))$
Let M be an $\epsilon$-NFA and let $S\subseteq Q$. Prove $\epsilon (S)= \epsilon (\epsilon (S))$.
I would like to prove this by contradiction but I don't know if my idea is correct.
Definition of $...
0
votes
1answer
40 views
DFA for language of all strings avoiding 'aa'
I'm trying to draw a dfa for this description
The set of strings over {a, b, c} that do not contain the substring aa,
current issue i'm facing is how many states to start with, any help how to ...
1
vote
1answer
66 views
What will be the pictorial diagram of this transition table?
I was doing my homework and I am confused on what I'm doing, it can't be that straightforward. I'm making a mistake somewhere. I tried looking for practice problems but they don't cover my issue ...
0
votes
0answers
26 views
Proving a language is Not Regular without using Pumping Lemma? [duplicate]
I was wondering how one would go about proving a language is Not Regular without using the traditional pumping lemma contradiction.
$$L = \{ 1^k 0^n 1^n 0^k \mid k \geq 0, n \geq 0\}$$
I've seen a ...
1
vote
3answers
67 views
All languages are regular, as unions of singleton languages
We know that singleton languages (languages containing exactly one word) are regular. We also know that a finite union of regular languages is also regular.
Suppose there is a non-regular language $L$...
1
vote
1answer
33 views
Finite / Infinite Languages True/False and why?
Just doing some work on Finite and infinite languages. And came across some statements I know the answer to but not sure how to explain why.
There are finitely many finite languages.
-This is false ...
0
votes
0answers
28 views
How to prove that L(G) is not regular by contradicting the pumping lemma?
I am trying to prove that this language is not regular by contradicting the pumping lemma. I have been reading and looking at examples but all the examples I have seen is in the for of a REGEX. I am ...
2
votes
1answer
31 views
If DFA has two states, which of the conditions hold?
Let $L$ be a regular language ,and $M = (Q, Σ, δ, q_0, A)$ is a DFA such that $L(M) = L$.
Prove that if $|Q| = 2$ then one of the following holds :
a) $L=∅$ b) $ε∈L$ c) $∃a∈Σ$ and $a∈L$
The problem ...
1
vote
1answer
50 views
Proving a DFA recognizes a language using induction
The following DFA recognizes the language containing either the substring $101$ or $010$. I need to prove this by using induction.
So far, I have managed to split each state up was follows:
q0: ...
2
votes
1answer
96 views
Method to construct a finite state machine for a finite-size language L
I need to define a method to construct a finite automata for a finite language L (part of my proof for something else).
My idea:
Create $|L|$ accepting states.
For each input string $s$ from $L$, ...
3
votes
1answer
63 views
Is Palindrome subset of a regular language regular?
Suppose we have $L$ being a regular language with alphabet $\Sigma$, if we define $M=\{ x \in \Sigma^{*} \mid xx^{R} \in L \}$, then we know that $M$ contains all half copies of palindrome strings ...
0
votes
2answers
44 views
No FSM/Regex exists for this language right?
The language is this:
$L = \{w \in \{a,b\}*:$ each $a$ has a matching $b$ somewhere in $w$ $\}$
This wouldn't have an FSM since you'd need infinite states of depth for each unmatched a you have, ...
2
votes
0answers
26 views
Minimal regular expression from minimal NFA for finite language in polynomial time?
Given a minimal NFA for a finite language, is there a polynomial-time algorithm to find a minimal regular expression for the same language?
This question is based on a recent question regarding ...
2
votes
1answer
33 views
General algorithm to find a minimal branching program
Given a general branching program, is there an algorithm which can find an equivalent branching program $P$ of minimal length. That is $|P| \leq |P'|$ for all equivalent branching program $P'$.
If ...
-1
votes
1answer
41 views
How to generate Deterministic finite automaton for given language
Problem: Write a program which generates Deterministic finite automaton which accepts given language. Language is defined with alphabet and start/end sub strings.
For example: Alphabet={a,b,c}; start ...
0
votes
0answers
56 views
If $L$ is a regular language then so is $L/a =\{w | wa ∈ L\}$, where $L$ is a language over $\Sigma$ and $a \in \Sigma$
I'm trying to work out a proof by construction that $L/a$ would be regular.
$a$ is any final symbol at the end of an accepted string, so I figured the only part of the machine that would have to be ...
0
votes
1answer
47 views
A regular expression for all strings that have exactly one double letter in them?
Why is the answer (b + /\)(ab)*aa(ba)*(b + /\) + (a + /\)(ba)*bb(ab)*(a + /\)? I'm confused and I request guidance
1
vote
1answer
43 views
Automata with minimal number of states using reverse
So, by the Bzozowski theorem, if A is DFA det(rev(det(rev(A))) would have minimal number of states. And for the most of them work. But for this example, I can't figure out why it doesn't. I have an ...
0
votes
1answer
22 views
Examples of Regular, Context-free and Context-sensitive languages
Assume the languages:
$$
a) \, L_1 = \{ w \in \{b,c \}^* | \, w \, \text{contains 'bbc' as substring} \}
$$
$$
b)\, L_2 = \{ 1^k 0^m 1^m | k,m \in \mathbb{N} \}
$$
$$
c)\,L_3 = \{ w \in {0,1}^* | \,...
1
vote
1answer
48 views
NFA that accepts 0* or 1*
Problem statement: Produce an NFA that accepts the strings 0* and 1*. So 000 and 11 would be accepted, while 101 would not be.
I'm a bit concerned about my idea because not all combinations of the ...
0
votes
0answers
16 views
Given a DFA M, formally define an NFA N such that L(N) = {x in L(M) | x = reverse(x)}
The english description of the question is (from my understanding) N accepts all strings that are both palindromic (the same forwards as it is backwards) and accepted by M. After a lot of toil and ...
-1
votes
0answers
29 views
Design a DFA to output Decimal Number
An input alphabet consists of the following symbols ONE, TWO, THREE,....,HUNDRED. Design a DFA that accepts input as the English language representation (e.g., ONE HUNDRED THIRTY FIVE) of any number ...
31
votes
2answers
2k views
Planar regular languages
In my class a student asked whether all finite automata could be drawn without crossing edges (it seems all my examples did). Of course the answer is negative, the obvious automaton for the language $\...
1
vote
1answer
35 views
Prove that a language is bounded if and only if it's finite
Let's assume $L$ is a language. $L$ is bounded if for some natural number $n \in \mathbb N$ applies $|x| ≤ n$, where $|x|$ is a length of a string, with every $x \in L$. Let's also assume that $L$ ...
2
votes
1answer
43 views
Prove: If finite automata M with k states accepts a string with at least k characters, then the language L(M) is infinite
I need to prove that if finite automata $M$ with $k$ states accepts a string with at least $k$ characters, then the language $L(M)$ is infinite. I have no idea where to start. Any suggestions?
0
votes
0answers
17 views
What classifier can recognize differences in two text strings immediately?
I'm playing around with the TextBlob library for python. It has in it a NaiveBayesClassifier as well as a ...
1
vote
1answer
22 views
Example of a locally trivial semigroup
I was having a look at the block product principle for finite monoids. I wanted to see the derivation of LTT = Acom$*$LI, using an example. But I can't come up with a non-trivial example of a monoid ...
0
votes
0answers
24 views
Uncommon case in Arden's lemma $q_{2} = 1q_{2} \cup 0q_{2}$
I'm trying to get the regular expression of an automata but an state has a form that I don't know how to solve, the form on its simplest example is:
$$q_{2} = 1q_{2} \cup 0q_{2}$$
What's the ...
2
votes
1answer
25 views
Computing epsilon-closure. What does $E(n) \leftarrow \{n\};$ and $E(p)$ mean?
I'm currently reading "Engineering a Compiler" book. In the chapter that explanes computing epsilon-closure there is listed the following algorithm:
But I couldn't understand what does $E(n)$ and $E(...
0
votes
1answer
36 views
Create automata from non regular grammar
I have two grammars:
L → ε | aLcLc
L → ε | aLcLc | LL
This two grammars are equals but the first one is regular, so it produces a regular language and a ...
0
votes
0answers
57 views
How to prove this language is not regular?
I am currently learning Pumping Lemma and found this question. But I am not able to prove it not regular. L = { $0^n$ | n is power of 2}. So, here I considered w = $0^{2^n}$ where n is constant of ...
1
vote
1answer
91 views
Write down a DFA for the regular expression (000* + 111*)* and explain why it cannot have lesser number of states
So, I came up with a DFA for the regular expression. Now for every string described by the regular expression, the DFA accepts it. But in order to ascertain if it's really a DFA for the regex, you ...
0
votes
1answer
27 views
Can you determinize an NFA in PSPACE?
QUESTION
Given some NFA $A$, can you simulate the determinization of it (using Subset-Construction for example) while remaining in $PSPACE$?
MORE DETAILS
I'm asking this as I want to be able to ...
2
votes
2answers
203 views
Proof: There exists an irregular language L such that LLLL is regular
As title.
I consider finding a specific L to fulfill the condition stated to prove the statement, however, I have no luck in finding one.
A senior gave me a hint that Lagrange's four square theorem ...
0
votes
0answers
27 views
Converting DFA to RE [duplicate]
I have been trying to solve this problem.
Convert the DFA to a regular expression.
I extracted these following equation.
$q_1 = q_2a$
$q_2 = q_1a + (a+b)q_3$
$q_3 = q_1b + q_2a $
Also,the ...
0
votes
0answers
36 views
Testing if a state is in final state
Please excuse my language, I am new to the topic.
I am trying to classify/find a class of game that describes games such as chess, tic-tac-toe as a finite state machine.
For those games, final ...
0
votes
0answers
30 views
Fastest algorithm that determines whether a given DFA is minimal? [duplicate]
NOTE - I can't find a good answer in the Similar question above ^
Given a DFA, is there a fast algorithm that determines whether it's minimal?
I'm looking for an algorithm that works faster than ...
0
votes
1answer
42 views
Number of final states in minimal DFA for $a^*b^*+b^*a^*$ [closed]
How many final states exist in the minimal DFA that accepts the language $a^*b^* + b^*a^*$?
2
votes
2answers
577 views
Why can't DFA's have 0 exiting arrows for some input symbols?
Suppose you are in a middle of computation on a non accepting state and at this point, an input of 0 is rejected by the DFA. But, according to Sipser's formal definition, you must still draw an ...
0
votes
0answers
27 views
why does the pumping lemma want us to only consider the first repitition of states?
In Sipser's Intro to Theory and computation, He writes:
I don't understand the constraint on x. Shouldn't it be just y <=p? (Equal bc in the case when machine M runs through all states p) Making ...
2
votes
2answers
32 views
Given an non-deterministic finite automaton, will its determinization always have unreachable states?
Given an NFA that accepts the regular language L, will its equivalent DFA which accepts the same language L always have unreachable states.
If it does, why?
1
vote
1answer
259 views
what is the difference between transition function (delta) and extended transition function (delta cap ) in finite automata
my doubt is
what is the difference between transition function (delta) and extended transition function (delta cap ) in finite automata ?
both of them when started at a state q for a string w will ...
5
votes
4answers
2k views
Are Finite Automata Turing Complete?
Something is Turing Complete if it can be used to simulate any Turing Machine.
So, can a Finite Automaton simulate a Turing Machine?
On the question Can regular languages be Turing complete? they ...
2
votes
0answers
81 views
Intersection of two deterministic parity automata
Given two deterministic parity automata $A_1=(Q_1,\Sigma,\delta,q_{01},c_1)$ and $A_2=(Q_2,\Sigma,\delta,q_{02},c_2)$ with the finite set of states $Q_i$, the finite alphabet $\Sigma_i$, the ...
1
vote
1answer
24 views
A deterministic FA for $0^*1^*$ is required
A deterministic finite automaton without $\epsilon$ steps for the language $0^*1^*$ is required.
Any nice picture ? I have created a NFA for this language which has 2 states $Q_1,Q_2$,
both are ...
2
votes
2answers
56 views
Is the language L = {(a,b)* | #a * #b is an odd number} regular?
Is the following language regular? $$\{ w \in \{a, b\}^* |\ \text{the product of the number of $a$'s and the number of $b$'s is an odd number}\} $$
If i'm not mistaken the condition is the same as ...
2
votes
1answer
23 views
Polynomial-time Compute the Number of States resulting from the NFA to DFA (greedy) conversion?
The canonical NFA to DFA conversion, starting with an NFA with $n$ states, can result in a DFA with $2^n$ states. However, in many cases, there are states that are "unnecessary," such as when ...
