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,333
questions
1
vote
1answer
10 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
11 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
26 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
18 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
29 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
57 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
21 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
42 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
34 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
50 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
157 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
104 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
43 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
39 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
77 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
59 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
57 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
25 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
61 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
69 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
45 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
43 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
34 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)...
0
votes
0answers
25 views
I can't seem to convert a NFA to a regex. What am I doing wrong? [duplicate]
I have the following diagram :
I try to remove state 3:
Now I do this:
What do I do now to get my regular expression? I'm stuck.
0
votes
2answers
29 views
In general, how does a DFA know how to successfully process a string the intended way?
Suppose we have:
$$A\text{ }\colon=\{x, y, z\}$$
$$M\text{ }\colon=\text{some DFA using A}$$
$$S\text{ }\colon=xyzxyzxyz$$
Intuitively, one might say $S$ is fed to $M$ on a per-character basis.
This ...
2
votes
2answers
56 views
Prove that every regular subset of $a^nb^n$ is finite
How to prove that every regular subset of $L=\{a^nb^n \mid n\ge0 \}$ is finite?
I know that every finite language is regular, and it's not true that every regular language is finite.
I also know that $...
1
vote
1answer
21 views
When can a Non-Deterministic Finite Automaton with Epsilon transitions considered to be in an accepted state?
A non-deterministic finite automaton is considered to be halted when either the whole input string has been consumed or when we reach a state where no available transition (if any) matches the current ...
2
votes
0answers
28 views
Regular string relations - proof of correctness
Let $T \subseteq \Sigma^* \times \Sigma^*$ be a regular (rational) relation. We define the obligatory rewrite relation over $T$ as follows:
$$
R^{obl}(T) := N(T) \cdot (T \cdot N(T))^*
$$
$$
N(T) := ...
0
votes
1answer
26 views
Convert the given NFA to DFA
I am trying to find an DFA for the regular language given by the expression $L\left( aa^{\ast }\left( a+b\right) \right)$.
First simplifying $L\left( aa^{\ast }\left( a+b\right) \right)$ we get
$L\...
0
votes
0answers
18 views
Mealy machine and moore machine
Can we compute the number of machine of two kind of transducers (mealy and moore) with $n$ states, and lenght of input symbols $m$, and lenght of output symbols $p$.
0
votes
0answers
20 views
About number of NFSTs
Can we proof the number of NFSTs with $n$ states : $n.2^{mpn}.2^{n}$ where $p$ is the cardinal of input alphabet and $m$ the cardinal of output alphabet.
1
vote
1answer
25 views
Is regex with backreference still able to be implemented by finite automata?
I recently learned that regex support backreference which enables referring to a matched group in the pattern itself. E.g. a regex (.)\1{2,} matches two or more ...
1
vote
1answer
23 views
Definiton of a certain symbol in a proof(The right linear languages are exactly the finite state languages)
I want to stress that i am not looking for a proof of this question, but rather if someone(that is familiar with the proof and it's context) can explain to me what the symbol 'e' means in the context.
...
-1
votes
1answer
20 views
How can I prove that the accepted language of a given DFA or NFA or REGEX is equivalent to a given language
I found this How do I verify that a DFA is equivalent to a NFA? but as it states it is not really a good question more of how can I check myself during an exam. Because as you might know to do this by ...
0
votes
1answer
27 views
Is there any property about height of PDA?
I'm trying to find a PDA for $L$ which modifies the stack height at most one.
$L=\{a^ib^i\mid i\geq 0\}$
I think there is no such PDA but how can I prove it?
My attempt is for a given string, find ...
0
votes
0answers
29 views
Is language bin(n)bin(2^(k+1) n + 1)^R context-free
I have a problem with this exercise. For language $$L_1 = \{ w \in \{0, 1\}^* : \exists k \in \mathbb N \ w = \text{bin}(n)(\text{bin}(2^{k+1}n + 1))^R \},$$ where $\cdot^R$ reverses a string and $\...
3
votes
1answer
67 views
Finding the upper bound of states in Minimal Deterministic Finite Automata
I have a task to determine the upper bound of states in the Minimal Deterministic Finite Automata that recognizes the language: $
L(A_1) \backslash L(A_2) $, where $ A_1 $ is a Deterministic Finite ...
0
votes
0answers
50 views
Does the order of ripping off the states matter?
Do we get same regular expressions at the end regardless of the order that we take the states step by step? Can somebody prove by exemplification?
0
votes
1answer
22 views
How to define an automata for zig zag concatenation? [duplicate]
I have two DFAs one for language A and one for language B.
I'm asked to make an FDA that is the zig-zag concatenation of letters of A and letters of B.
This is described by the following: {w: w = $a_1 ...
0
votes
2answers
17 views
Regular languages, automata
I want to ask about the definition of regular languages. My book says there has to exist a deterministic finite automaton that recognizes it. Does this mean the finite automaton recognizes exactly ...
1
vote
1answer
86 views
Zigzag concatenation of two languages
Given two regular languages $A,B$ on the same alphabet $\Sigma$, I want to show that the following language is regular:
$$
\{a_1b_1 \ldots a_kb_k \in \Sigma^* \mid a_1,\ldots,a_k,b_1,\ldots,b_k \in \...
-1
votes
1answer
32 views
Proof for palindrome grammar by induction
I can't seem to find a solution to the following question.
Given the following grammar for palindromes:
$$G_{pal}=\{\{a,\dots,z\},\{P\},P,R\},$$ with $R$ consisting of the rules
...
0
votes
2answers
21 views
NFA that ends with 0 and doesn't have 11 after the first 0
So as the title says i m trying to find this NFA. So far i thought to make an NFA that "guesses" what comes after the first 0 and i got this:
After some time trying to get rid of all the extra (7 !)...
3
votes
1answer
113 views
Why is this language a regular language?
Came across this in a book, and I'm wondering why the following language is regular?
$$ L = \{a^nww^R: n \geqslant 0, w \in \{a,b\}^3\}$$
Is it correct to say that $$ \{a^n : n \geqslant 0\} $$ is a ...
0
votes
2answers
44 views
Regular expression for a palindrome of finite length?
I have a language $$ L = \{ww^R, w \in \{ab\}^5\}$$
I know this is a regular language because it is finite (since w can only be of length 5). I want to prove it's a regular language, so I'd create a ...
1
vote
1answer
23 views
I'm asked to draw DFA for this {$\epsilon$, 0} however I do not understand what {$\epsilon$, 0} mean
I'm asked to draw a DFA of this {$\epsilon$, 0} but have no clue what it means. Can someone help me understand what the automata is supposed to do?
I know that $\epsilon$ is the symbol for empty ...
