# 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,358 questions
Filter by
Sorted by
Tagged with
43 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 ...
17 views

### Convert finite automata to regular expression

I am trying find the regular expression that describes the finite automata in the image below. Given the following finite automata which of the following regular expressions describes the same ...
15 views

### Regular language is closed given transposition of rightmost character to leftmost

It would appear straightforward to show that a regular language is closed given the transposition of the rightmost character to the front. However after drawing a few sample DFA for the phenomenon, I'...
223 views

### Closure of regular languages under deleting a 1 from each even run of 1s

Let $R$ be a regular set over the alphabet $\{0, 1\}$. Give a machine construction to prove that the set obtained by deleting one 1 from each even length block of 1’s is also regular, and using ...
10 views

### I'm having some trouble converting a FA to a RegEx [duplicate]

I was reviewing some of the material that I found about FA to RegEx and while I was practicing with one or another conversion, I came across this FA that I could not pass to RegEx. Would someone be so ...
14 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 ...
19 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 ...
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.
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 ...
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 ...
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 ...
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 }
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 ...
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=...
1k views

### Counting the number of words accepted by an acyclic NFA

Let $M$ be an acyclic NFA. Since $M$ is acyclic, $L(M)$ is finite. Can we compute $|L(M)|$ in polynomial time? If not, can we approximate it? Note that the number of words is not the same as the ...
27 views

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 ...
29 views

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 ...
62 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 ...
53 views

### Prove that a language is decidable

I need some help to prove that the language is decidable. $K$ = {$N$ : $N$ is a DFA (Sigma = {a, b, c}) and $L$($N$) contains at least one word in which there is no a}. It tried to make an algorithm ...
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|\...
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$ ...
74 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 ...
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 ...
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 ...
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 ...
129 views

### Brzozowki's algorithm doesn't work for this corner case

I'm a newbee learning DFA minimization. And I found that(strangely) Brzozowki's algorithm cannot give me a minimized DFA on this example: In this DFA, $S_0$ and $S_1$ are nondistinguishable and ...
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 ...