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.

learn more… | top users | synonyms (2)

0
votes
1answer
32 views

What is the regular expression of this language? [duplicate]

$\Sigma = \{0, 1\}$ $L = \{x$| $x \in \Sigma^* $ $\&$ $ \#_0(x) = 3$ $or$ $ \#_1(x) = 3 \}$ What is the regular expression of this language? At first I thought $r = (0+1)^*0(0+1)^*0(0+1)^*0$ $...
0
votes
1answer
20 views

Simple regular expression problem [duplicate]

new to automata theory and this is quite difficult for me so I'd appreciate a hint in the right direction if possible. We want to find a regular expression for the language $L$ over $\Sigma = {a,b,c}$...
3
votes
1answer
58 views

How to Trace Path in Proof that Regular Languages are Closed Under Reversal

I'm self studying automata theory and I need help with proving that regular languages are closed under reversal. I have a basic proof, but am unsure about last statement in my proof. Is this ...
2
votes
2answers
38 views

Size comparison of NFA and minimal DFA [duplicate]

Except for isomorphisms, the minimal DFA of a regular language is unique. However, is it possible that an equivalent NFA has less states than the minimal DFA? If so, what is the reasoning behind this? ...
-1
votes
2answers
127 views

Finding nfa or dfa for a language [duplicate]

I'm trying to study for the summer ahead of class I saw this question, please how do I go about it? Find NFA/DFA for the language $L = \{0^n1^n : n \in N\}$
-2
votes
2answers
46 views

Find a DFA for a finite set of palindromes

Since every finite language is regular, I'm trying to find how would a DFA for the following language $\{xx^R \mid x \in \{a,b\}^*, |x| = \ell\}$ look like. Would there be one DFA for all words of ...
1
vote
1answer
44 views

NFA to accept strings where the third AND the third-last element are b

Alphabet is {a,b}, the third element from the start must be "b" (e.g: aab..., abb...) and the third-last element must also be "b" (e.g: ...baa, ...bbb). I can do them separately but at the same time I ...
-4
votes
1answer
71 views

Order classic notions of computability by power

I need some help with a question. I'm currently studying for an exam and I could therefore use some help with this following question: Order the following formalisms (but one) according to their ...
-2
votes
1answer
31 views

Convert regular expression to FA?

I am trying to solve a practice problem from my textbook which is to draw an FA from this language: L(ab* a*) U L((ab)*ba) I need help to draw the second part L((ab)*ba). I know the shortest string ...
1
vote
2answers
34 views

What is the expressive power of finite-state transducers and pushdown transducers?

One would assume that a finite state transducer can perform any translation such that the resulting string is from a regular grammar. Similarly, that a pushdown transducer can generate strings from ...
-1
votes
1answer
97 views

Regular expression for language of strings having odd length but even number of $b$'s [duplicate]

I have to draw a finite automaton of a language over $\{a,b\}$ of all strings having odd length and has an even number of $b$s. I already came up with following regular expression $(a+b)((a+b)(a+b))^*...
-1
votes
1answer
27 views

Subsets and Proper subsets of regular language

Let L ⊆ {0, 1}* . Then 1) If all proper subsets of L are regular,is L regular? 2) If all finite subsets of L are regular,is L regular? 3) If a proper subset of L is not regular,is L non regular? I ...
1
vote
1answer
35 views

Finding the Regular Expression of a language

I'm trying to find a regular expression for the language $$L = \{w\mid n_a(w)+n_b(w)\equiv 2\pmod3\}\,,$$ where $n_a(w)$ is the number of $a$s in $w$. I can see that this would generate strings of ...
1
vote
2answers
74 views

Write a regular expression - Contains an equal number of 01 and 10 subtrings

I have this language: And ive worked on a DFA where i can move on to create the RE. Here is my DFA: What im trying to do now is using ardens theorem to get the Regular expression however I'm ...
0
votes
0answers
32 views

Minimize NFA with epsilon transition

I have an NFA with epsilon transition, I would remove the epsilon transitions, but I do not know if I have to use Hopcroft algorithm or another algorithm. Can you help me? Thanks
1
vote
1answer
32 views

What name for an algorithm is more correct: Kleene's algorithm or McNaughton-Yamada algorithm?

The perhaps most widely known algorithm converting finite automata into rational expressions is usually known as Kleene's algorithm. However, Sakarovitch in his book Elements of Automata Theory ...
7
votes
1answer
460 views

Is it possible to build DFA for odd-length words with 1 in the middle?

$L := \{w \in \{0,1\}^* | $the length of $w$ is odd $ \wedge $ 1 is in the middle of $w\}$ So the alphabet is $\{0,1\}^*$. My problem is that I can't keep track of the equality of chars before and ...
1
vote
0answers
56 views

Construct DFA given oracle access to the language

I was given the following question. Given a minimal DFA $A$ with $m$ states over some alphabet $\Sigma$ which is a "black box" (you can only run words to it and it tells you if it accepts or not): ...
3
votes
1answer
69 views

Where Can I Find DFA Practice?

Where can I find a web site or book where I can practice drawing DFAs from a language like " {w| w has at least three a’s and at least two b’s} ". It will be important to have access to the answer so ...
0
votes
2answers
72 views

If L is a regular language, how to prove that L' is also regular?

I've been trying to construct a proof of the following statement the whole day but I got stuck: If $L$ is a regular language, the language $L_{}{'}$ consisting of all words in $L$ containing the ...
0
votes
0answers
30 views

Is the language of all DFAs that accept the empty language regular?

Is $E_{DFA}$ in the class of regular languages? $\qquad E_{DFA} = \{ \langle D \rangle \mid D \text{ is a DFA }, L(D) = \emptyset\}$ My argument is that it is because all of the DFAs in $E_{DFA}$ ...
1
vote
1answer
16 views

What is the effect of having a transition in an epsilon-NFA upon “$\epsilon$,0”?

When a transition between two states is achieved via any of the symbols $\epsilon,0$, how does the $\epsilon$ effect the transition between the two states? Does it simply mean that the $0$ is ignored,...
1
vote
2answers
27 views

similar language by two DFA then why wrong answer

I attempted a mock paper for finite automata .so i was asked to create a DFA which accepts a language in which inputs are a,b and number of b's should be divisible by 3.The first image is my answer ...
1
vote
1answer
30 views

Design the grammar for the following [closed]

Design the grammar for the following: L = (a^n)w(w^r)(b^n) where n>=0 and w={a,b}
6
votes
1answer
42 views

What does Cellular Automata Pre-image problem actually means?

I am reading about Cellular Automata and Computational Complexity and i found a related paper by F. Green, NP-Complete Problems in Cellular Automata. In the 2nd page he lists three NP-Complete ...
6
votes
2answers
109 views

How similar are two DFAs? -not just binary equivalence-

Are there any measures to compute similarity (or distance) between two DFAs? If yes, which are the main references? I need a measure of similarity, not only a (binary) equivalence test. "Similarity"...
4
votes
3answers
53 views

What is the difference between finite automata and Büchi automata?

as the title suggests, I was struggling to define the differences between finite and Büchi automata and how they are represented. From an assignment I'm working on, this automaton can be depicted ...
-1
votes
1answer
46 views

construct a dfa that accepts odd consecutive number of 0's and 1's

this dfa should accept only consecutive odd number of both 0's and 1's. example: 10001,1110001,10,01,011101. How can I draw its diagram?
0
votes
1answer
30 views

Isomorphism of a DFA and the minimal DFA

I have a DFA A, I minimize A and the minimized DFA obtained is M. My question is if in general A and M are isomorphic?
0
votes
3answers
92 views

Design an NFA to accept a, ad, abc, abd, but not e, abcd?

I've made the following diagram to accept a, ad, abc, abd but I don't it to accept e, abcd, how can I limit that? Updated I modified the diagram in another attempt:
1
vote
1answer
83 views

PDA for all non-palindromic strings of even length

I had a homework assignment where I had to build a PDA over the alphabet $\{a,b\}^*$, accepting $L = \{x \mid x \text{ is even but not a palindrome}\}$. I already turned it in, but I know I had it ...
1
vote
1answer
37 views

Removing $\epsilon$ transitions in a NPDA

NPDA's and general NFA's may not halt for finite inputs like DFA's do because of their $\epsilon$ transitions. However, NFA's with $\epsilon$ transitions could be converted to those without any $\...
1
vote
1answer
93 views

How do I describe a DFA?

Consider the alphabet E = ${[abc] : a, b, c \in 0,1,...,9)} $ Example [234], [567], [897] are symbols of the alphabet. For a string $w \in $ let n(w) denote the number represented by $ w $: ...
2
votes
3answers
69 views

Proof that whether a regular language is finite is decidable

I have this question for a homework. The question stems from the fact that you can determine whether a regular language is empty by using a Turing machine to count the states n in the given FSM. When ...
-1
votes
1answer
67 views

Show that if S is an arithmetic progression, then A can be recognized by a DFA [duplicate]

A set S of nonnegative integers is called an arithmetic progresion if there exist some integers n and p such that S = {n + ip : i ≥ 0} Let A ⊆ {a}∗ and consider S = {| x |: x ∈ A}. (1) Show that if ...
0
votes
0answers
28 views

Regular expression for C-style /**/ comments [duplicate]

I am aware that a similar question was already asked here and that the recent question A DFA for recognizing comments is also related but I am not satisfied with the answers. The point is that ...
3
votes
3answers
61 views

Regular expression for a binary string containing even number of 0's

To get the regular expression I made a finite automata as the following (not sure if you can directly write regular expression without it): The regular expression for the above according to me ...
-1
votes
1answer
31 views

Why do these NFAs need epsilon transitions?

In the picture below, I'm trying to figure out why there's a need of epsilon in there and what would be the difference if we didn't put epsilon.
2
votes
1answer
40 views

Difference between a minimal DFA and a canonical DFA

given a language L,a DFA M that recognize L is minimal if M is the DFA with the minimum number of states. In order for this to happen M does not have neither unreachable nor equivalent states. The ...
1
vote
1answer
52 views

Regular expression for a finite automaton appears to be wrong

For the following finite state machine: The language recognized by it is given to be: $0+(10+11)(0+1)^*$ in my samples book, which I think is clearly wrong, since there's no return path to the ...
2
votes
1answer
50 views

How to write the turing machine processing operations?

I have this Turing machine example given in my book: For the language $0^n1^n$. I understand how it works because it's very similar to a Finite State Machine. But what I want to know is the ...
0
votes
1answer
51 views

If L is a regular language then the language replace(L,σ,τ) is also regular

I am stuck at the following problem: Prove that if $L$ is a regular language over some alphabet $\Sigma$ and that $\sigma, \tau \in \Sigma$, Then the language $replace(L,\sigma,\tau)$ is regular. ...
-3
votes
1answer
16 views

Equivalence of DFA' definitions

According to wikipedia DFA accepts word $w$ by one of two definitions: A word $w$ is accepted by $M$ if $\hat\delta(q_0,w)\in F$. A word $w=w_1w_2\dots w_n$ is accepted by $M$ if $\exists r_0,\dots,...
0
votes
1answer
37 views

What happens when ε-clos(X) contains duplicate elements? Example: (1+0)*1

I am learning about state machines from the Stanford online cs143 course. Here I have tried to build a nondeterministic finite automaton for the regular expression ...
2
votes
2answers
43 views

Closure under reversal of regular languages: Proof using Automata

I have been studying the closure properties of regular languages, referencing the book Introduction to Automata Theory, Languages, and Computation by John E. Hopcroft and Jeffery D. Ullman. Under the ...
1
vote
1answer
28 views

A regular expression for an automaton which accepts strings with no more than 3 consecutive zeros [duplicate]

This is the automaton I want to find the regular expression for: As you see, states Q1 to Q4 are accepted and Q5 is a kind of trap. This automaton accepts strings that have no more than 3 ...
3
votes
2answers
43 views

An NFA with no equivalent DFA with fewer than $2^n$ states: Example and Proof

I have been following the book Introduction to Automata Theory, Languages, and Computation by John E. Hopcroft and Jeffery D. Ullman. I came across the following topic titled Bad Case for Subset ...
-1
votes
1answer
53 views

Can a DFA just have one state that is both the initial state and the final state?

so im trying to create a DFA for a language that has an infinite number of possible strings over the alphabet {a,b}. can i not just have one state (initial and final state) that loops a,b to itself? ...
3
votes
1answer
68 views

How many languages exist over a finite alphabet?

I'm currently reviewing my Automata and Languages Theory course and I stumbled upon the following exercise exams. Link In "Exercises for ACS 1, Fall 2004, sheet 1", exercise 1 item C, the question is,...
4
votes
1answer
163 views

Brzozowski algebraic method for NFA

Currently I have a graph (basically, a state graph) in Scala which is similar to an NFA some nodes have multiple in/outgoing edges single start state there might be multiple final states a state ...