Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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
vote
1answer
18 views

Simple property of DFAs

Do you know if this simple property of a DFA is stated as a property (or theorem) in some Automata theory book (possibly with a particular name)? Property: Given a DFA $A = \{ Q, \Sigma, \delta, q_0, ...
1
vote
1answer
12 views

How to check if DFA is actually a correct model of the intended system?

Suppose I have modeled a deterministic finite automaton of my system. How can I check if the traces generated by this system, actually represent the model I had in mind? For example, say I have DFA ...
0
votes
0answers
23 views

Deterministic Finite State Automata - Benefits of using DFA to typical software coding and testing [on hold]

Suppose I have modeled the behavior of my system by Deterministic Finite Automaton (DFA) A, and I need to check if it satisfies a safety condition. I have created another DFA S, which represents the ...
1
vote
1answer
46 views

Why are those very similar languages in a different complexity class?

i am having a real time understand why the following two languages are in two different complexity classes(the first is NP-Hard and the second is in P). tried to look online at various resources and ...
0
votes
3answers
73 views

Define a finite automaton accepting the language below

$\{ w∈(a,b)^\ast | w $ does not contain '$ab$' as a subword $\}$. About questions like this, I always want to construct the regular expression for it, then convert the regular expression to a finite ...
1
vote
1answer
17 views

State Transition Diagrams for XOR

I have found two different versions for State Transition Diagrams for XOR. I'm confused as to why one has 2 states and the other has 3. What are the implied states in each please? Are they both ...
1
vote
0answers
31 views

Characterization of NFA whose equivalent (minimal) DFA has exponential number of states

(I don't know if there are standard names for this, so) Let's say that a Nondeterministic Finite Automaton (NFA) is $n$-expansive if it has $n$ states and any Deterministic Finite Automaton (DFA) ...
-1
votes
0answers
43 views

dfa modulo 6 don't work correctly [closed]

this dfa accepts the multiples of 6 in binary, I have tried it and it works with 0,6,12,18,24,30,36. this dfa accepts 0000, 0110,100,10010,11,000,11110 and 100100. the dfa has only worked correctly ...
2
votes
1answer
18 views

Modelling regex replacement via a DFA

I wish to model the following common construction in code via a finite state automaton for the purposes of static analysis: ...
-2
votes
0answers
35 views

Give a regular expression for language L [closed]

guys! I am studying formal language now. There is a question: Give a regular expression for language L={a,bb,aa,abb,ba,bbb...}. Can anyone give me some advice? Thanks in advance!
2
votes
2answers
38 views

Is intersection used in regular expression?

As union is part of regular expression in form of positive closure, similarly intersection is also a part of regular expression? in which form it can be used?
0
votes
0answers
53 views

How to find the minimum number of states of a deterministic finite automaton accepting a given language [duplicate]

Let $L$ be a language over $\Sigma$. And $\Sigma = \{0,1\}$ is a set of input alphabets. $L = \{ w \mid w \in \Sigma^*, \text{ where $w$ is a string with numbers of 0s divisible by 3 and number of ...
0
votes
0answers
9 views

Arden theorem with 3 input [duplicate]

I have just started learning Arden's theorem to convert finite automata but I am stuck on its execution when we have 3 inputs. Because I am not able to simplify any equation to have only 2 inputs ...
1
vote
1answer
42 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 ...
3
votes
1answer
69 views

Is the language of words with equal number of 010s and 101s as substrings regular?

Is the language of words containing same number of 101s and 010s regular? If yes, how can I design a DFA for it? In general, is the language of words containing equal number of strings which one is "...
1
vote
3answers
51 views

Is it possible to define a DFA for the language of words having exactly one double letter? [closed]

Consider the language $\{ w \in \Sigma^*~|~ w~\text{contains exactly one double letter}~\}$. For example, $baaba$ has exactly one double letter, but $baaaba$ has two double letters. Suggested answer ...
0
votes
0answers
53 views

proving DFA stuck

This DFA fulfills: Define a function $diff: \{0,1\}^*\to\Bbb Z$, for $w \in\{0,1\}^*$, $diff(w)=($# of 1's in $w)- ($# of 0's in $w$). Thus, $diff(\epsilon)=0$; $diff(0)=−1$; $diff(1)=1$. Let $L = ...
6
votes
2answers
1k views

Is there a reasonable and studied concept of reduction between regular languages?

Have been any interesting formulations for the concept of reduction between regular langauges, and if so -- are there regular-complete languages under those reductions?
0
votes
0answers
34 views

dfa subtract multiple of 3 [duplicate]

Define a function 𝑑𝑖𝑓𝑓 ∈{0,1}→ℤ so: for everything w ∈{0,1}, diff w = # of 1's in w- # of 0's in w. Thus: 𝑑𝑖𝑓𝑓 𝜀=0; 𝑑𝑖𝑓𝑓 0=−1; 𝑑𝑖𝑓𝑓 0=−1; Let 𝐿 = {𝑤∈ {0,1} * | 𝑑𝑖𝑓𝑓 𝑤 = 3𝑚 ...
3
votes
2answers
72 views

One counter automaton as a function

We can associate a one counter finite automaton with a function $f:\Sigma^* \to \mathbb{N} \times \{0,1\}$, where $f(x)=(n,b)$ describes the state where the automaton terminates when fed an input word ...
0
votes
0answers
11 views

How to understand DFA's and how to understand how to construct them based on a given regular language? [duplicate]

I have practiced DFA's for an upcoming test and I haven't been able to grasp how to construct more difficult DFA's. An example would be this question : Construct a deterministic finite state automata ...
4
votes
1answer
243 views

Irregularity of language of prefixes of decimal expansion of pi

Let $L_{\pi}$ be the language consisting of prefixes of the decimal expansion of $\pi$: $$L_\pi = \{3, 31, 314, 3141, 31415, 314159, \ldots\}.$$ Prove that Lπ is not DFA-recognizable. You may use the ...
1
vote
1answer
28 views

Do all DFA's containing an “accepting path containing a cycle” accept infinite languages?

So I've seen this claim being made on different questions: Do self-loops in DFA cause infinite languages? I'd like to find formal proof for this. I think I should also note that an "accepting path ...
0
votes
0answers
27 views

Show that the following languages are equal [duplicate]

I have the following exercise: Prove that $\{ab,aba\}^*=\{\epsilon\} \cup \{a\}\{ba,baa\}^*\{b,ba\}$. My idea was to write the words of each of the languages in the following way,for example for the ...
0
votes
0answers
38 views

construct regular expression for a language [duplicate]

I want a regular expression for the following language. (a+b+c)*, but does not contain substring "abab". That means it can be any combination of (a, b, c) except "abab". I tryed to construct it ...
7
votes
1answer
104 views

Proof of Brzozowski's algorithm for DFA minimization?

Brzozowki's algorithm is cited widely. Several questions here give examples or discuss its complexity. But I haven't been able to find a proof of correctness for the algorithm. How do we prove it ...
0
votes
1answer
27 views

Unifying Accept States in NFA

I recently read the first question and answer in this homework solution https://cseweb.ucsd.edu/classes/sp08/cse105/hw2s.pdf However, I am not sure if for example, you have two accepting states ...
0
votes
0answers
25 views

Analyzing the encoding of a DFA by a deterministic Turing machine [duplicate]

Define $L=\{\langle D,R \rangle \mid D$ is a DFA, $R$ is a regular expression, $L(D)=L(R) \}$ Is $L$ decidable? Is $L$ decidable in polynomial time ($L \in P$)? I am trying to ask: can a TM analyze ...
1
vote
1answer
17 views

In an FSA, can you have more than one transition for the same symbol from a single state?

My textbook asks: Consider the sets of strings on $\{0,1\}$ where the 4th symbol from the right end is different from the leftmost symbol. Construct an accepting FSA. The answer it provides ...
2
votes
1answer
33 views

Confused about pumping lemma

Here I have the method for pumping lemma to prove that a language $L$ is not regular: Suppose to the contrary that L is regula, then $\exists$ DFA $A$, s.t. $L(A) = L$. Let $n$ be the number of ...
5
votes
4answers
93 views

Proving non-regularity of $\{a^p \mid p \in \text{Prime} \}$ without pumping lemma

I was wondering whether it is possible to prove $\{a^p \mid p \in \text{Prime} \}$ is a non-regular language without using the pumping lemma. I'm having trouble choosing an alphabet that completes the ...
3
votes
1answer
39 views

Nested word automatons

At the moment I'm trying to understand nested word automatons but I don't get the point quiet right. Let's say I have the alphabet $\Sigma = \{c,r\}$ and I want ot recoginize the languge $\mathcal{L} ...
3
votes
1answer
65 views

Automaton recognizing ambiguously accepted words of another automaton

Let $A$ be a nondeterministic automaton. Let $X(A)$ the set of words for which there at least two accepting paths. In one of the previous exam, for which no answers are available, it is required to ...
0
votes
1answer
70 views

Decide if a string is in a language without simulating the automata accepting the languge

Is it possible for a Turing machine with input of a DFA that accepts a finite language and a string to decide whether the string is in the language without "fully simulating" the DFA on the string? ...
1
vote
2answers
39 views

DFA & RE from descriptive definition of given regular language

I am trying to make the DFA and RE of a regular language which is define on the alphabet = {1,0} and all the strings present in these languages have exactly one 010 substring in them. Some strings ...
1
vote
2answers
29 views

Number of final states in a minimal DFA

Is the number of final states in a DFA at least the number of final states in its minimal DFA? Is the answer even yes? Any help would be appreciated.
2
votes
2answers
111 views

DFA which accepts all strings starting and ending with 'aa'

I have to construct a DFA which accepts set of all strings over {a,b} which start and end with 'aa'. I have constructed the following DFA, but it does not accept 'aa' and 'aaa'. How can I make it ...
2
votes
1answer
62 views

Initial States in Moore Machine?

I went through the rules of Moore and Mealy Machine or FA. I read that both could have one initial state and no final state. If Moore Machine has one initial state then there is a problem for ...
2
votes
2answers
71 views

DFA of (aa+bb)(a+b)* + (a+b)*(aa+bb)?

Our class teacher gave us a descriptive definition of a language in a Quiz today and ask us to make its DFA. In the middle of quiz he also told us the Regular Expression(RE) of that language but we ...
0
votes
0answers
15 views

Find whether a word is in a rational expression

You are given a word $w$ and a rational expression $R$ ($R$ is represented as a binary tree). Find an efficient algorithm that says whether $w \in L(R)$ or not. I think I found a quadratic algorithm. ...
2
votes
1answer
29 views

Why every rational langage is the image of a local automaton

I have seen this result but I don’t understand why it’s true : Every rational language is the image of a local language by a morphism : $\phi : \Sigma^{*’} \to \Sigma^*$ I know what a local ...
2
votes
1answer
64 views

Simple way to prove $\left \{ 0^{n}1^{m} \mid (n-m) \bmod 5=0 \right \}$ is regular?

Prove: $\left \{ 0^{n}1^{m} \mid (n-m) \bmod 5=0 \right \}$ is regular. Is it reasonable to get a DFA with at least 30 states for this language? is there an easier way to prove it is regular?
2
votes
2answers
48 views

Is there a way a proving a language regular/non-regular that works for every possible language?

In my theory of computing class, we've been talking about how to prove languages regular and non-regular. I've heard of methods like the pumping lemma and Kolmogorov complexity to prove languages non-...
0
votes
1answer
20 views

Behavior of specific PDA for a certain input

Suppose we're given the non-deterministic PDA shown below which reads from the alphabet $\sum = \lbrace a,b \rbrace$. How will this PDA behave if we pass it the string $ba$? We read $b$ first and push ...
1
vote
1answer
46 views

Why language is not regular

Taken from site "Geeks For Geeks". The lemma: "A concatenation of pattern(regular) and a non-pattern(not-regular) is also not regular language." example: $\left \{L={a^{n}b^{2m}|n\geq 1,m\geq 1} \...
1
vote
1answer
45 views

Is {xy | x, y ∈ Σ∗ and x contains more a’s than y} regular?

I've been asked to write a DFA for: $\{xy\mid x, y \in \Sigma^*\text{ and }x\text{ contains more }a\text{’s than }y\}$ where $\Sigma=\{a,b\}$. I don't believe this is possible. Can anyone confirm if ...
2
votes
2answers
66 views

Having a better complexity / adversary argument for finding if a finite automata accepts a palindrome

Let $A$ be a DFA over a finite alphabet $ \Sigma$. Find an algorithm that indicates if $A$ accepts a palindrome and give the complexity of this algorithm. Here is my solution: If we denote $^t A$ ...
3
votes
2answers
35 views

Can the pumping lemma for context free languages be extended to any subword?

It is known that in the case of a Regular Language $L$ , the pumping lemma can be extended to apply to any sufficiently long subword of the language, ie, if $uwv \in L$ and $|w| \ge p$ then we can ...
1
vote
1answer
20 views

Identifying the Equivalence Classes of a Language with equal number of 10 and 01 strings

I'm doing a problem where I need to find the equivalence classes of the language below: Let A = {x ∈ {0, 1}* | #(01, x) = #(10, x)}, where, for a, b ∈ {0, 1}*, #(ab, x) is the number of places in x ...
0
votes
0answers
25 views

Is there a known lower bound on the time/space complexity of DFA minimization?

I've read the Wikipedia page on the topic, but there's no mention of a lower bound on the time complexity, and there's no mention of space complexity at all.