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,218
questions
0
votes
0answers
26 views
How specifically do I need to describe (in words) the language of a regular expression?
For the regular expression $(a*ba*b)*a*$, I want to learn how to describe it in words. I know there are an even number of $b$s but how much do I need to explain it? Do I need to explain it enough that ...
2
votes
1answer
71 views
How many different languages over the unary alphabet {a} are recognized by 2-state DFAs?
I am struggling to answer the following question:
How many different languages over the unary alphabet {a} are
recognized by 2-state DFAs?
According to the textbook, the hint was to first ...
-1
votes
0answers
41 views
Is this language over 0s and 1s regular?
The language L = {xyx, where x,y are arbitrary strings over {0,1}}.
Is this a regular language?
How can this be shown?
11
votes
2answers
2k views
Can a DFA have an unreachable state?
I am trying to prove or disprove the following statement:
If $A = (\Sigma, Q, \delta, q_0, F)$ is a complete DFA where $F \neq \emptyset$ then $L(A) \neq \emptyset$
So my initial thinking is to ...
2
votes
0answers
57 views
Which of these languages is regular? The Pumping Lemma seems to show none are
I've been reviewing past paper questions for an automaton course, and came across a question which effectively asks, which of these languages is regular?
$$
\{\ 0^m1^{(m \times n)}0^n\ \colon\ m,n\ge ...
2
votes
1answer
22 views
NFA equality for automata with partial transition functions and all states accepting
Given two nondeterministic finite state automata with partial transition functions, such that all states are accepting, except for the implicit failure sink state, is it possible to decide in ...
1
vote
1answer
18 views
How to construct a DFA which accepts all the strings endig with aa and no two consecutive b (bb)
I have to construct a DFA which ends with aa and does not contain any pair of b-s. A = {a,b}, {aa,baa,aaa,abaa,babaa,...}. I know how to construct them as separate DFAs but not together merged.
-2
votes
2answers
33 views
Deterministic Finite Automaton
design a DFA accepting the set of strings over the alphabet {0, 1} that when interpreted in reverse as a binary integer, are divisible by 3
1
vote
1answer
45 views
Kleene star operations
Let $𝚺$ be any alphabet and let $𝑳_𝟏 \subseteq 𝚺^{∗}$ and $𝑳_2 \subseteq 𝚺^{∗}$ be two non-empty languages.
a. If $𝑳_𝟏 𝚺^{∗} \neq 𝚺^{∗}$ than what can we say about $L_1$.
b.Let $\Lambda \...
1
vote
1answer
32 views
Need help with previous “Automata / Theory Of Computation” exam question
I passed by this question in a previous exam while studying for the "Automata / Theory Of Computation" and I am struggling to find answer. I would appreciate it if someone can help me with it:
This ...
2
votes
1answer
57 views
Finding the union, subtraction, and intersection of two DFAs
I recently solved problem of finding union of two DFAs and came up with some observations. I need confirmation about them along with some other facts:
I can prepare the union, subtraction and ...
2
votes
1answer
46 views
PSPACE-completeness of DFA intersection problem
Let some deterministic finite automata be given. There is a problem of determining whether the intersection of these DFA is empty, and I want to show its PSPACE-completeness.
It seems to me that I ...
0
votes
2answers
47 views
When Turing Machine behaves like Finite state automaton
I read following:
Turing Machine with finite (fixed sized) tape is essentially Finite state automaton.
Is this fact correct? My doubt is Turing Machine can go infinite loop even on finite tape if ...
2
votes
1answer
92 views
Prove/disprove: If $𝐿_1$ is a finite language but not empty and $𝐿_2$ is NOT regular then $𝐿_1 \circ 𝐿_2$ is NOT regular
That what I have so far, but I am not sure at all.
Assume toward contradiction that $𝐿_1 \circ 𝐿_2$ is regular.
Define $\Sigma' = \{\sigma'|\sigma\in\Sigma\} $.
Define a regular substitution $\...
1
vote
1answer
35 views
Are every 2 DFAs with $n$ states for a language $L$ isomorphic to each other?
Consider 2 DFAs both determining a language $L$. Both DFAs have the same number of states $n$. Can I then conclude that these two DFAs are isomorphic?
I think the answer is yes, because if I'd make ...
-1
votes
0answers
64 views
DFA that accepts all the strings that either begin or end (or both) with 01
I came across following problem:
Minimum number of states in DFA that accepts all the strings that either begin or end (or both) with 01 over the alphabet {0,1} = ?
I first tried to prepare two ...
3
votes
2answers
51 views
Are DFAs with a unary alphabet strictly less powerful than DFAs with a binary alphabet?
Are DFAs with a unary alphabet strictly less powerful than DFAs with a binary alphabet? Is this even a meaningful question?
For example, if $\Sigma = \{\texttt{0}, \texttt{1}\}$, we can encode any ...
0
votes
0answers
27 views
DFA question regarding memory and states
I have to program a DFA which has to do the following for an input of binary 5 my task told me to use a finite memory
0 0 1
1 2 3
2 4 0
3 1 2
4 3 4
qi−1 δ(qi−1,0)...
0
votes
1answer
30 views
Copy operation in under 9 states?
There is a long row of cells. Each cell contains 0 or 1. A machine is positioned immediately to the right of a series of uninterrupted 1’s followed by an uninterrupted series of 0’s. In the following ...
8
votes
2answers
788 views
Length of strings accepted by DFA
Problem: Given a DFA $D$, find all possible lengths of strings accepted by the $D$.
It makes sense that these lengths can be represented as $a_i+kb_i$. What might be the algorithm to find all such ...
0
votes
1answer
43 views
How create DFA with multiple finished states for lexers?
Is possible to create DFA directly from regular expression. But for lexical analyse is needed "joined" DFA with many finish states, for example one state for string, one for integers, one for floats ...
0
votes
0answers
14 views
NDFA has maximum states as 2^n the same for qubits in quantum computation.How they can be distinguished in means of computation? [duplicate]
I am a Computer Engineer. I studied basics of Quantum Computation. In dealing with multiple states, I feel NDFA does similar to Quantum Computation but we preferred to convert NDFA to DFA and solved ...
0
votes
0answers
16 views
Regularity of language of words of prime length [duplicate]
Is the following language regular?
$$
L_{\mathit{prime}} = \{ w \in \{0,1\}^* : |w| \text{ is prime} \}.
$$
I have to either provide a DFA (if the language is regular), or prove that it is not ...
0
votes
1answer
45 views
Language to regex
Let A={a,b}.
So the question is to write regular expression such that L(r) which consists of all words.
My answer is this:
L(r)= (a+b)* a* b* (a+b)*
Is this ...
0
votes
1answer
30 views
Deterministic pushdown automaton for a given language
I am trying to make a deterministic pushdown automaton from this language but without success.
Here is the language definition:
$\ L=\{0^n 1^m a^i b^j \ /\ m,n,i,j > 0 \ and \ m+n=i+j \} $
...
2
votes
1answer
111 views
Why does $L = \{ 0^n 1^n \space | \space n \in \mathbb{N} \}$ belong to $\mathrm{P}$?
My professor said that the non-regular language $L_{1} = \{ 0^n 1^n \space | \space n \in \mathbb{N} \}$ belongs to $\mathrm{P}$. I do understand that all regular languages belong to $\mathrm{P}$ as ...
2
votes
2answers
48 views
Does any algorithm loops at some point?
Given that any implementable algorithm has a finite number of internal states, and given that any state is determined by the previous one, does that implies that any algorithm loops at some point?
If ...
3
votes
1answer
28 views
Converting DFA to RE with Arden's Rule
So I've searched around and found the algorithm to do so: How to convert finite automata to regular expressions? and I decided to test out the second-level response, Raphaels, and while I was getting ...
0
votes
1answer
22 views
Can nfa consume more than one letter at a time
If I have a NFA/DFA and I expect inputs of 00, 01, 10, 11 can I read input in groups of 2 binary digits at a time.
like the example shown
0
votes
1answer
26 views
NFA/DFA for $ L= \{a^n b^n a | n\ge0\}$
I have made two DFA’s for $ L= \{a^n b^n a | n\ge0\}$.
First one has several states. The second one is accepting an empty string also.
Somebody please guide me the correct one.
Zulfi.
0
votes
2answers
12 views
Regular expression containing lambda
What is the meaning of lambda here:
$$(b+c)^*(a+\lambda)(b+c)^*(a+\lambda)(b+c)^*(a+\lambda)(b+c)^*$$.
I know that lambda is used in the context of NFA?
Let's suppose we break down the expression ...
0
votes
0answers
23 views
Intersection of two DFA's
I am trying to understand the intersection of 2 DFA's. I got the following link:
Intersection of 2 DFAs
I can't understand why they have not used the symbol 'b'. In the DFA's they have symbol 'b' also ...
0
votes
0answers
22 views
What exactly is “pattern matching”?
I know some examples of "pattern matching". E.g. in the context of functional programming, and regular expressions.
But is there a precise definition?
In particular, it seems that it has to do with ...
1
vote
1answer
54 views
Meaning of $a\lor b \to b' \lor c'$
So I have done part a) but I have no clue what I am supposed to do for part b), I have been trying for days to wrap my head around and even asked my fellow course mates, none of which seem to know ...
0
votes
0answers
23 views
Use ML to create a graph
I'm currently looking for literature/papers on machine learning techniques to create structures.
In detail, I want to generate finite automata (NFA, DFA), which are useful for student-exercises. So I ...
0
votes
1answer
84 views
Determine if an NFA accepts infinite language in polynomial time
Question Statement: Given a NFA $N$, design an algorithm that runs in polynomial time such that it determines if $L(N)$ is infinite.
(Note that converting NFA to DFA is exponential time).
For any DFA,...
0
votes
0answers
28 views
Why does this finite state machine state transition diagram solution has more states than my solution?
I can't figure out what is wrong with my solution and why does it differ from book's solution. I think the only thing that matters is the previous state of A so that there should be two states, one ...
0
votes
0answers
21 views
Possible number of DFAs, NFAs, DPDAs, NPDAs, NDTMs and DTMs for various input parameters
I came across problem asking for possilble number of DFAs for a given number of states and alphabet. I started guessing if we can find possible number different automatas for given number of states, ...
0
votes
1answer
41 views
No nonfinal states in NFA
I know that if there are no non-final states in DFA then the language accepted is $\Sigma^*$.
What will happen if there are no non-final states in an NFA? Can we say it also accepts $\Sigma^*$? Can ...
1
vote
2answers
53 views
Pumping Lemma with Prime Number [closed]
$\text {Could someone please help me with this proof: }$
$L:=\left\{a^{n} d^{m} b^{k} | n, m, k \in \mathbb{N} \wedge m \text { is a prime number}\right\}$
$\text {Maybe we can say, that } w=a^{n}d^{...
1
vote
1answer
29 views
Closure of regular languages under “inverse second half”
Theorem. Show that if $L$ is regular, then so is
$$
\varphi(L)=\left\{w \in \Sigma^{*} \mid \text {there exists an } \alpha \in \Sigma^{*} \text { with }|\alpha|=|w| \text { and } \alpha w \in L\...
0
votes
0answers
22 views
Minimal DFA for “$n$th character from the right is $a$” [duplicate]
I am given the following regular expression, which accepts all strings over $\{a,b,c\}$ whose $n$th character from the right is $a$:
$$ (a|b|c)^*a(a|b|c)^{n-1}. $$
The exercise asks for the number ...
2
votes
1answer
50 views
Regular expression for language that does not accept x string (3 letters, |x|=3)
The language I am interested in is $L=\{w∈\{a,b,c\}^*| w$ contains "$bac$" but not "$cab$"$\}$. I am thinking that the result will have the form $L=X_1X_2X_3$, where $X_1=\{w∈\{a,b,c\}^*| w$ does not ...
1
vote
1answer
66 views
Can a dfa return only the final state?
I am given an assignment to design a tiny arithmetic unit (from 0 to 15 inclusive) start with 0 and using a DFA. The operations are as follow:
increment x+1 and if x+1 is larger than 15 then x+1 ...
1
vote
1answer
42 views
What kind of language does the following DFA accept?
can anyone please describe the language this FA accepts? thank you
2
votes
1answer
48 views
Does this argument prove CFLs are not closed under union?
Context free languages are not closed under complementation. This follows from their property of non-closure under intersection:
If CFLs were closed under complementation, then they must have also ...
2
votes
2answers
137 views
Prove that the following language is not regular: $\{0^i1^j : i \neq j\}$ [duplicate]
I was trying to approach this proof, after multiple reads and attempts I am getting nowhere. If someone could help me out that would be great. Should I use the pumping lemma, if so how show I start, ...
0
votes
0answers
30 views
Backwards and forwards automata languages compared with regular languages
Is every language accepted by a BAFDA regular? I am not even sure what the answer is. I tried thinking around canonical examples of non-regular languages (like $0^n1^n$ or $\{ww | w \in \{0,1\}^{*}\}$ ...
2
votes
0answers
21 views
Why are VFSMs not more commonly used?
For a job several years ago I worked with a team using technologies built around Virtual Finite State Machine models for system fault analysis and remediation. Since then, I've found it to be a ...
1
vote
1answer
26 views
Are number of states in a NFA same as Pumping length?
So i was reading a post on Minimum pumping length of regular language where Yuval Filmus has proved that a pumping lemma might have lesser number of states than a minimal DFA. But What about NFA's? ...
