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,220
questions
1
vote
2answers
39 views
How Intersection of Regular Language and a CFL is a CFL?
CFL is not closed under intersection. That means, if we have L1,L2 of CFL then
L1 intersection L2 is not a CFL
And we know, all Regular languages are CFL. Then ...
0
votes
0answers
28 views
What is the strongest arithmetic theory decidable by a DFA, DPDA or PDA?
It is known that WS1S can be decided by a DFA. Is this the strongest arithmetic theory decidable by a DFA? What happens when the automata class is extended to include DPDAs or PDAs?
1
vote
1answer
54 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 ...
2
votes
1answer
75 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
58 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
21 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
38 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
62 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
48 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
69 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
40 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
790 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
46 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
32 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
112 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
29 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
55 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
90 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
29 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
43 views
What kind of language does the following DFA accept?
can anyone please describe the language this FA accepts? thank you
2
votes
1answer
51 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
146 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
32 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\}^{*}\}$ ...
