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,355
questions
0
votes
1answer
18 views
DFA to accept a String containing even number of both A and B, but rejects empty String
I want to draw a DFA to accept a String containing even number of both A and B, but rejects the empty String(ε)
I have already drawn the DFA which accepts the above language, without rejecting the ...
-2
votes
0answers
15 views
Regular Expression (RE) [duplicate]
Define the Regular Expression of the combination 0 and 1, whereas every 0 always followed by
11 or 111.
1
vote
1answer
31 views
DFA and equivalence relation
I was studying Theory of Computation and I'm kind of lost in solving this problem.
Let $R$ be a relation defined on the set of states $Q$ of a DFA as $q_1Rq_2$ if $\delta(q_1,a)=\delta(q_2,a)$ for ...
1
vote
0answers
17 views
Is $L = \{ w : \#_a(w) = \#_b(w) \}$ regular?
Is $L = \{ w : \#_a(w) = \#_b(w) \}$ regular? I do not think it is. I recently posted a question and from there I was thinking if this language is regular.
If we assume on the contrary, then there ...
1
vote
2answers
24 views
Operations without common elements can not be generated using a finite state automata
I heard that some operations involving regexes that do not have common elements can NOT be generated using a finite automata. I do not remember what it was, where it was from, can anyone tell me what ...
0
votes
0answers
14 views
Is that a regular express? Proof using closure properties or pumping theorem [duplicate]
I am studying regular express. I understand how to proof a xa ya. However, I don't know how to proof the below problem. Please help me.
L = { xa yb | a ≠ b }
0
votes
1answer
20 views
Is (a+b)* and (ab)* same in finite automata?
Regular language of (a+b)* and (ab)* are:
(a+b)* = { ε, a, b, aa , ab , bb , ba, aaa, ...}
(ab)* = { ε, a, b, aa, ab, ba, bb, aaa, ... }
I am new to Finite automata and this simple notion is ...
0
votes
2answers
30 views
What does this language notation specify?
I am given this exercise:
Let L1 ={akbk : k > 0} and L2={ck : k > 0}. For each of the following strings wi, state and explain whether or not wi ∈ L1L2.
w1=ε
w2=aabbcc
w3=abbccw
w4=aabbcccc
w5=...
1
vote
2answers
27 views
Proving a language with equal occurences of ab, and cd is not a regular language using the Pumping Lemma
I am trying to show that $A = \{w \in \{a,b,c,d\}^{*}|w \textrm{ has equal occurences of } ab \textrm{ and } cd\}$ is not regular by using the Pumping Lemma.
My idea here was to use the string $ s = (...
1
vote
1answer
23 views
Applying the Pumping Lemma to aspecific string
Given the language $ A = \{w \in \{a,b\}^{*} | w = w^{R}\}$ (i.e. palindromes using the symbols $a, b$), I am trying to determine if the Pumping Lemma can be applied to strings of the form $s = a^{2p}$...
0
votes
0answers
40 views
NFA recognizing strings in $\{0,1\}^*$ that have two zeros separated $4i$ characters, for some $i\geq1$
I am trying to design a nondeterministic finite automaton that recognizes the language of strings in $ \{0,1\}^{\ast}$ that have two zeros separated by a string of length 4i, for some $i \geq 1$.
Let $...
0
votes
2answers
22 views
string concatenation vs language concatenation
What exactly is the difference between
$$
C = \{a^*\}\{b\}\{a^*\}\{b\}\{a^*\}\{b\}
$$
and
$$
D = \{a^nba^nba^nb | n \geq 0 \}
$$
It is known that D is non-regular and C is regular, but I am not sure ...
2
votes
2answers
28 views
How to we prove if a right linear language is ambiguous?
Considering the following language as an example:
$$\begin{align}
S &\rightarrow aS \mid bA \\
A &\rightarrow bA \mid aB \mid aD \mid \varepsilon \\
B &\rightarrow aB \mid \varepsilon \\
D ...
0
votes
1answer
26 views
Read regular Expression from NFA
Good evening everyone!
Can someone help me with the following task?
So we have this NFA:
I was supposed to create a regular expression out of it. Now the solution says: $a^{+}b^{+}(c|ca^{*}b^{+})^{*}$...
0
votes
1answer
91 views
What is the the pumping length for the regular expression (0+0001)((1111)*+(00)*)
I have this assignment question to find the pumping length of a regular language (L). The regular expression for the L is given as
$(0+0001)((1111)^*+(00)^*)$
What is the length of the longest string ...
2
votes
3answers
42 views
How to use DFA/NFA to prove the language {$0^n 𝑥1^𝑛$ | x ∈ Σ*, n ≥ 1} is regular?
I'm trying to prove the language L = {$0^n 𝑥1^𝑛$ | x ∈ Σ*, n ≥ 1} is regular, but don't know how to present it in a DFA/NFA.
I'm thinking to have n+1 states in a NFA, with the start state as the ...
0
votes
1answer
24 views
minimum number of states in cross product of two minimum DFAs
If FA1 and FA2 are 2 DFAs with minimum number of states. I want to find cross product DFA (FA1XFA2). Will the cross product DFA obtained from 2 minimum DFAs also have minimum number of states(num of ...
1
vote
2answers
46 views
How to prove that concatenating a language A and A* is commutative?
Suppose we have a language $A$. I want to prove that $AA^*$ is commutative. I know that this expression equals $A^+$, but I'm not sure how to go about a proof yet. This is my attempt so far.
If $A$ is ...
0
votes
0answers
81 views
Generalization of automaton - Sipser example 1.33
I am trying to construct a nfa that generalizes Example 1.33 found in the book Introduction to the Theory of Computation by Sipser, but I am quite sure
that my transition function is wrong. I'd like ...
0
votes
0answers
28 views
Building an NFA where where proceeding part of string has same or more 1's
Having trouble figuring out a NFA for the following language, the objective is to use only 3 states:
$L = {\{1^ky : y \in \{0,1\}^* }\text{ and y contains atleast k 1's, for k} \ge 1 \}$
I have got to ...
1
vote
1answer
36 views
Expert explanation of state elimination methods [duplicate]
I'm so sorry if this question is too general, but I need to understand the general process of the "State elimination method".
In other words, what is the general idea, and what is the ...
1
vote
2answers
35 views
How are useless states created NFA to DFA
So I understand how to convert an NFA to a DFA, however my question is, on a conceptual level, how and why are useless states created, and how can you (if there is a way) convert an NFA to a DFA ...
0
votes
1answer
36 views
Understand the DFA: accepting or not accepting “aa” or “bb”
I want to discuss the strings accepted by couple of DFAs:
DFA in Figure 1 has 3 final states. It looks like that it accepts both the substrings "aa" (q0q3q0q1) or "bb". So this is ...
2
votes
1answer
12 views
Sufficient condition for $xy^*z \subseteq L$ for a DFA with $n$ states
In chapter 2 of the New Turing Omnibus, the author considers an unknown finite automata with 6 states. Through trial and error, it is deduced that the words 0101, 0100101, 0100100101 are accepted. It ...
1
vote
2answers
13 views
PDA for a language where the second part is not the reverse of the first part
I came across an exercise for constructing a PDA for the following language:
$$L = \{ncm \mid n,m\in\{a,b\}^* \text{ and } n \ne m^R\}.$$
Where $L \subseteq ({a,b,c})^*$
So $n$ and $m$ are both a ...
-3
votes
0answers
28 views
Question relating to NFA
Is there any NFA that can accept every alternate symbol in a given string.
Ex. if w = abab, the NFA should accept bb
1
vote
1answer
19 views
A regular language derived from another
This is similar to a previous question I asked, but doesn't seem aminable to the same technique. Given a regular language $A$, show the following language is regular:
$$
\{x|\exists y \; |y| = 2^{|x|} ...
0
votes
1answer
32 views
Can this language be called regular?
Recently, I was facing some problems in effectively proving the following :
Consider the alphabet Σ ={0,1,2,...,9,#}, and the language of strings of the form x#y#z, where x,y and z are strings of ...
0
votes
2answers
61 views
How can I efficiently construct a CFG from a language
I am new to CFG's and automata in general and I came across an exercise where I needed to construct a CFG for the language {a^m b^n | n <= m + 3}.
So m can be infinitely bigger than n but n can ...
1
vote
1answer
28 views
Regularity of a language constructed from a know regular language
I'm working through so textbook questions on regular languages, and came across a problem that amounts to showing the following language is regular, given that $A$ is a regular language:
$$
\{x|\...
1
vote
1answer
25 views
Construct a DFA recognizing a language $L$ that has exactly $I(L)$ states
Let $L$ be a language, and consider the following relation $\equiv_L$ on strings:
$s_1 \equiv_L s_2$ if and only if, for every string $w$, we have that $s_1w \in L \Leftrightarrow s_2w \in L$.
This is ...
1
vote
1answer
48 views
Clarification on an Hopcroft book DFA minimization example
At page 156 there is an example on how to find the distinguishable states for the following automaton:
The following table shows the distinguishable states:
By applying the given definition for ...
1
vote
1answer
81 views
Check if a NFA accepts a string of non-prime length
Given a nondeterministic finite automaton $A$, give an algorithm that checks whether the language $L(A)$ decided by $A$ contains a string whose length is a composite (i.e. not prime) number.
My ...
0
votes
1answer
52 views
What language does this deterministic finite automaton accept?
Been mulling over this one for hours, my initial thought was { w ε {a,b}* | w is empty, or ends with either ab or ba} but that's clearly wrong as neither aba nor bab are accepted by the automaton. If ...
2
votes
1answer
60 views
Extracting regex submatch boundaries without backtracking
I'm attempting to develop from scratch a simple regex engine. I would like for my engine to have the ability to report, "The regex matched on a substring of this line starting at index and ...
4
votes
1answer
160 views
Show $L = $ { w $\in (a,b) ^* $| for every u substring of w, $-5\le|u|_a−|u|_b\le5\}$ is regular
I try to show that this language is regular:
$L = $ { w $\in \ (a,b) ^ * $| for every u substring of w, $-5\le|u|_a−|u|_b\le5\}$
If I build a NFA and run on it every substring of w (skip other letters ...
3
votes
2answers
106 views
Is it possible to construct a finite state automata for a decimal adder?
Suppose the strings are of the form x#y#z , where x,y,z are strings formed from the alphabet $\Sigma=(0,1,2,3,4,5,6,7,8,9)$ . The language is accepted if x+y=z is satisfied, for example : 56#65#121 is ...
-2
votes
1answer
46 views
running RAM on a given input
I understand how RAM commands work but I am unable to understand how we use a given input string and find the output. For instance,
there's a Random Access Machine which has an input {0,1}*. The ...
0
votes
1answer
41 views
For an NFA, can we always find a RAM?
For an NFA, can we always find a RAM, which recognises the same language?
0
votes
1answer
82 views
building NFA for { a^p; p is a prime number, m is a fixed number and m >p >0 }
$\{a^p; p$ is a prime number, $m$ is a fixed number and $m\geq p \geq 0 \}$
I know this is regular since it is finite, but I don't understand how to build an NFA for this if we do not know what $m$ ...
0
votes
1answer
60 views
Proof that $\{0|1\}^*0\{0|1\}^n$ requires at least $2^{n+1}$ states
How can you prove that any DFA accepting the language generated by the regular expression $\{0|1\}^*0\{0|1\}^n$ requires at least $2^{n+1}$ states?
I first attempted induction on $n$. But I don't ...
0
votes
1answer
73 views
In an NFA, what if there are no transitions out of an accept state but there are symbols left in the string?
Let's say I have a string 0110 and after 011 I reach an accept state (let's call the accept state "q") in an NFA. However, there is no transition mentioned in the diagram from q for the ...
0
votes
0answers
28 views
Why is there no contradiction when using pumping lemma on a^N b^N a^2N, when k=2?
I have question where it asks:
Using the pumping lemma on a^N b^N a^2N, why can you not reach a contradiction when k=2?
Here's what I've done, but I do reach a contradiction...
u=a^r
v=a^s
x=a^t b^N a^...
1
vote
2answers
62 views
Does a regular expression exist for any number that contains no more than two 5s and no 6 twice in a row?
For example, a valid number would be 6165156 and an invalid number would be 1566515.
I have tried many times to construct a finite state machine for this with no success, which leads me to believe the ...
0
votes
2answers
88 views
Is checking if regular languages are equivalent decidable? [duplicate]
Is this problem algorithmically decidable?
L1 and L2 are both regular languages with alphabet $\Sigma$. Does L1 = L2?
I think that it is decidable because you can write regular expressions for each ...
0
votes
0answers
46 views
Is it necessary for a Push down Automaton (PDA) to have a stack?
I am given a Finite Automaton and the question is to design an Equivalent PDA for it. This is my FA:
Is this PDA correct or do I need to add a stack to it? If its right when is the stack needed?
0
votes
1answer
44 views
How to define enumeration of the set of finite state machines?
I want to write a function that takes N (maximum number of states) as a parameter, enumerates all possible finite state machines up to N states, and returns random FSM with a probability in proportion ...
1
vote
0answers
43 views
How design a Deterministic finite automata which accept string starting with 101 and how to draw transition table for it if there is a dead state
I’m trying to design a DFA
which accept string starting with 101 if the string start with 0 then it goes to dead state.Is my design is correct or wrong? And I don’t know how to draw transition table ...
1
vote
0answers
34 views
k-limited solution for PCP
So there's following problem, that has been bugging me for the last few days:
A solution of a PCP $ i_{1},\dots,i_{n}$ with the cards $(x_{1} ,y_{1}),\dots,(x_{m}, y_{m})$ is considered as $k$-...
1
vote
2answers
31 views
Computing automaton for $L(A) / L(B)$ gives ones for $A,B$
I'm trying to figure out whether infinite language change the answer.
Show that the following language is decidable:
$$L=\{\langle A,B \rangle : \text{$A,B$ are DFAs, $L(B)$ is finite, and $L(A)/ L(B)...
