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
0
votes
1answer
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 ...
0
votes
1answer
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 ...
1
vote
1answer
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'...
3
votes
1answer
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 ...
0
votes
0answers
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 ...
1
vote
2answers
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 ...
0
votes
1answer
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 ...
-2
votes
0answers
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.
1
vote
1answer
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 ...
1
vote
0answers
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 ...
1
vote
2answers
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 ...
0
votes
0answers
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 }
0
votes
1answer
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 ...
0
votes
2answers
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=...
9
votes
2answers
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 ...
1
vote
2answers
27 views

Proving a language with equal occurences of ab, and cd is not a regular language using the Pumping Lemma

I am trying to show that $A = \{w \in \{a,b,c,d\}^{*}|w \textrm{ has equal occurences of } ab \textrm{ and } cd\}$ is not regular by using the Pumping Lemma. My idea here was to use the string $ s = (...
1
vote
1answer
25 views

Applying the Pumping Lemma to aspecific string

Given the language $ A = \{w \in \{a,b\}^{*} | w = w^{R}\}$ (i.e. palindromes using the symbols $a, b$), I am trying to determine if the Pumping Lemma can be applied to strings of the form $s = a^{2p}$...
2
votes
3answers
42 views

How to use DFA/NFA to prove the language {$0^n 𝑥1^𝑛$ | x ∈ Σ*, n ≥ 1} is regular?

I'm trying to prove the language L = {$0^n 𝑥1^𝑛$ | x ∈ Σ*, n ≥ 1} is regular, but don't know how to present it in a DFA/NFA. I'm thinking to have n+1 states in a NFA, with the start state as the ...
0
votes
0answers
40 views

NFA recognizing strings in $\{0,1\}^*$ that have two zeros separated $4i$ characters, for some $i\geq1$

I am trying to design a nondeterministic finite automaton that recognizes the language of strings in $ \{0,1\}^{\ast}$ that have two zeros separated by a string of length 4i, for some $i \geq 1$. Let $...
0
votes
2answers
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 ...
2
votes
2answers
29 views

How to we prove if a right linear language is ambiguous?

Considering the following language as an example: $$\begin{align} S &\rightarrow aS \mid bA \\ A &\rightarrow bA \mid aB \mid aD \mid \varepsilon \\ B &\rightarrow aB \mid \varepsilon \\ D ...
0
votes
1answer
96 views

What is the the pumping length for the regular expression (0+0001)((1111)*+(00)*)

I have this assignment question to find the pumping length of a regular language (L). The regular expression for the L is given as $(0+0001)((1111)^*+(00)^*)$ What is the length of the longest string ...
0
votes
1answer
26 views

Read regular Expression from NFA

Good evening everyone! Can someone help me with the following task? So we have this NFA: I was supposed to create a regular expression out of it. Now the solution says: $a^{+}b^{+}(c|ca^{*}b^{+})^{*}$...
0
votes
1answer
24 views

minimum number of states in cross product of two minimum DFAs

If FA1 and FA2 are 2 DFAs with minimum number of states. I want to find cross product DFA (FA1XFA2). Will the cross product DFA obtained from 2 minimum DFAs also have minimum number of states(num of ...
0
votes
1answer
73 views

Multiple paths for a accepting string in NFA?

If a string(w) is accepted by an NFA, then corresponding to w, can there be multiple paths each starting from the start state and ending at an accepting state?
5
votes
3answers
3k views

Is {wxw^r} a regular language?

Is $\{ WxW^{\mathrm{R}} \mid W,x\in\{0,1\}^+\}$ a regular language? If so, why? The notation $W^{\mathrm{R}}$ means the reverse string of $W$? If we consider the best answer in this solution, ...
1
vote
2answers
48 views

How to prove that concatenating a language A and A* is commutative?

Suppose we have a language $A$. I want to prove that $AA^*$ is commutative. I know that this expression equals $A^+$, but I'm not sure how to go about a proof yet. This is my attempt so far. If $A$ is ...
1
vote
1answer
36 views

Construct regular expression that contains the substring

I need to write a regular expression for the following set of strings on Σ = {a, b, c} in which the number of b’s is even, and contains abcba as a substring. So far, the even number of b's can be ...
0
votes
0answers
81 views

Generalization of automaton - Sipser example 1.33

I am trying to construct a nfa that generalizes Example 1.33 found in the book Introduction to the Theory of Computation by Sipser, but I am quite sure that my transition function is wrong. I'd like ...
0
votes
0answers
29 views

Building an NFA where where proceeding part of string has same or more 1's

Having trouble figuring out a NFA for the following language, the objective is to use only 3 states: $L = {\{1^ky : y \in \{0,1\}^* }\text{ and y contains atleast k 1's, for k} \ge 1 \}$ I have got to ...
1
vote
1answer
36 views

Expert explanation of state elimination methods [duplicate]

I'm so sorry if this question is too general, but I need to understand the general process of the "State elimination method". In other words, what is the general idea, and what is the ...
1
vote
2answers
35 views

How are useless states created NFA to DFA

So I understand how to convert an NFA to a DFA, however my question is, on a conceptual level, how and why are useless states created, and how can you (if there is a way) convert an NFA to a DFA ...
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 ...
-1
votes
1answer
38 views

What strings does this language accept/reject?

F = {ww | w ∈ {0,1}^*} Which strings are accepted and why? 0011 1010 1111
2
votes
1answer
12 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
315 views

Over the alphabet {a,b,c,d}, how would i construct a NFA that only accepts strings that end with a letter that is already part of the string?

I've been trying to create a NFA that accepts strings that end with a letter that exists in the string. For example abcdb, cbdd, acac etc. while strings like abc aacd etc are not accepted since the ...
-3
votes
0answers
28 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
19 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
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 ...
0
votes
2answers
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 ...
-1
votes
1answer
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 ...
1
vote
1answer
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|\...
0
votes
1answer
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$ ...
0
votes
1answer
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 ...
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 ...
1
vote
1answer
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 ...
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
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 ...
1
vote
1answer
87 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 ...
15
votes
4answers
7k views

Why is NFA minimization a hard problem when DFA minimization is not?

I know that we can minimize DFAs by finding and merging equivalent states, but why can't we do the same with NFAs? I'm not looking for a proof or anything like that--unless a proof is simpler to ...

1
2 3 4 5
28