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.

Filter by
Sorted by
Tagged with
11
votes
2answers
3k 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
76 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
49 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
53 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
55 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
0
votes
2answers
74 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 \...
0
votes
1answer
51 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
361 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
107 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
190 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
191 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
60 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 ...
3
votes
2answers
94 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
46 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
55 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
1k 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
56 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
46 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
40 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 \} $ ...
1
vote
1answer
140 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
50 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
46 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
34 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
50 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
64 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
44 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
29 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
74 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
27 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
434 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
32 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
26 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
190 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
88 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
49 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 ...
3
votes
3answers
84 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
93 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
77 views

What kind of language does the following DFA accept?

can anyone please describe the language this FA accepts? thank you
2
votes
1answer
112 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
1k 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
47 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
26 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
109 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? ...
5
votes
2answers
218 views

Finding the number of distinct strings in regular expression

Given the regular expression $(1 + \varepsilon + 0 )(1 + \varepsilon + 0 )(1 + \varepsilon + 0 )(1 + \varepsilon + 0 )$, how many distinct strings are in the language? How do you determine this from ...
24
votes
7answers
11k views

Why is English not a regular language?

Surely any language with a finite longest word can be made regular by having an automaton with paths to 26 states for all letters and then having each of those states go to another 26 states, etc., ...
2
votes
1answer
39 views

totally ordered semigroups

Given a semigroup is it possible to give a total order to it? If not possible in the general case then what about the case of finitely generated finite semigroups? Does there exist a natural ...
3
votes
1answer
132 views

How do I solve these questions regarding homomorphism?

Questions: Give an example of a homomorphism, using the same alphabet, ฮฃ, for both languages A and B. Now, give a second example of a homomorphism but this time using two different alphabets, ฮฃ and ...

1 2 3
4
5
โ€ฆ
28