The Stack Overflow podcast is back! Listen to an interview with our new CEO.

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
-1
votes
0answers
27 views

Draw an NFA over {0,1}

if I want to design a NFA (that's NOT A DFA) that accepts the set of all strings that do not contain the substring 1010, is this correct? because I can just accept 1010 by capturing it in the starting ...
-1
votes
1answer
41 views

Constructing a DFA of strings that are in A but not in B

I am tasked with creating a DFA for the regular language L = A/B, which are the strings that are in A but not in B. The alphabet is Σ = {a,b,c} I am not really sure where to even start with this one, ...
0
votes
0answers
39 views

How do I convert the regular expression to a state digram?

I need to code an automaton that is equivalent to this expression: ('+'|'-'| )(D+ | D+ '.' D∗ | D* '.' D+) where ...
1
vote
1answer
52 views

Let M be an $\epsilon$-NFA and let $S\subseteq Q$. Prove $\epsilon (S) = \epsilon (\epsilon (S))$

Let M be an $\epsilon$-NFA and let $S\subseteq Q$. Prove $\epsilon (S)= \epsilon (\epsilon (S))$. I would like to prove this by contradiction but I don't know if my idea is correct. Definition of $...
0
votes
1answer
40 views

DFA for language of all strings avoiding 'aa'

I'm trying to draw a dfa for this description The set of strings over {a, b, c} that do not contain the substring aa, current issue i'm facing is how many states to start with, any help how to ...
1
vote
1answer
66 views

What will be the pictorial diagram of this transition table?

I was doing my homework and I am confused on what I'm doing, it can't be that straightforward. I'm making a mistake somewhere. I tried looking for practice problems but they don't cover my issue ...
0
votes
0answers
26 views

Proving a language is Not Regular without using Pumping Lemma? [duplicate]

I was wondering how one would go about proving a language is Not Regular without using the traditional pumping lemma contradiction. $$L = \{ 1^k 0^n 1^n 0^k \mid k \geq 0, n \geq 0\}$$ I've seen a ...
1
vote
3answers
67 views

All languages are regular, as unions of singleton languages

We know that singleton languages (languages containing exactly one word) are regular. We also know that a finite union of regular languages is also regular. Suppose there is a non-regular language $L$...
1
vote
1answer
33 views

Finite / Infinite Languages True/False and why?

Just doing some work on Finite and infinite languages. And came across some statements I know the answer to but not sure how to explain why. There are finitely many finite languages. -This is false ...
0
votes
0answers
28 views

How to prove that L(G) is not regular by contradicting the pumping lemma?

I am trying to prove that this language is not regular by contradicting the pumping lemma. I have been reading and looking at examples but all the examples I have seen is in the for of a REGEX. I am ...
2
votes
1answer
31 views

If DFA has two states, which of the conditions hold?

Let $L$ be a regular language ,and $M = (Q, Σ, δ, q_0, A)$ is a DFA such that $L(M) = L$. Prove that if $|Q| = 2$ then one of the following holds : a) $L=∅$ b) $ε∈L$ c) $∃a∈Σ$ and $a∈L$ The problem ...
1
vote
1answer
50 views

Proving a DFA recognizes a language using induction

The following DFA recognizes the language containing either the substring $101$ or $010$. I need to prove this by using induction. So far, I have managed to split each state up was follows: q0: ...
2
votes
1answer
96 views

Method to construct a finite state machine for a finite-size language L

I need to define a method to construct a finite automata for a finite language L (part of my proof for something else). My idea: Create $|L|$ accepting states. For each input string $s$ from $L$, ...
3
votes
1answer
63 views

Is Palindrome subset of a regular language regular?

Suppose we have $L$ being a regular language with alphabet $\Sigma$, if we define $M=\{ x \in \Sigma^{*} \mid xx^{R} \in L \}$, then we know that $M$ contains all half copies of palindrome strings ...
0
votes
2answers
44 views

No FSM/Regex exists for this language right?

The language is this: $L = \{w \in \{a,b\}*:$ each $a$ has a matching $b$ somewhere in $w$ $\}$ This wouldn't have an FSM since you'd need infinite states of depth for each unmatched a you have, ...
2
votes
0answers
26 views

Minimal regular expression from minimal NFA for finite language in polynomial time?

Given a minimal NFA for a finite language, is there a polynomial-time algorithm to find a minimal regular expression for the same language? This question is based on a recent question regarding ...
2
votes
1answer
33 views

General algorithm to find a minimal branching program

Given a general branching program, is there an algorithm which can find an equivalent branching program $P$ of minimal length. That is $|P| \leq |P'|$ for all equivalent branching program $P'$. If ...
-1
votes
1answer
41 views

How to generate Deterministic finite automaton for given language

Problem: Write a program which generates Deterministic finite automaton which accepts given language. Language is defined with alphabet and start/end sub strings. For example: Alphabet={a,b,c}; start ...
0
votes
0answers
56 views

If $L$ is a regular language then so is $L/a =\{w | wa ∈ L\}$, where $L$ is a language over $\Sigma$ and $a \in \Sigma$

I'm trying to work out a proof by construction that $L/a$ would be regular. $a$ is any final symbol at the end of an accepted string, so I figured the only part of the machine that would have to be ...
0
votes
1answer
47 views

A regular expression for all strings that have exactly one double letter in them?

Why is the answer (b + /\)(ab)*aa(ba)*(b + /\) + (a + /\)(ba)*bb(ab)*(a + /\)? I'm confused and I request guidance
1
vote
1answer
43 views

Automata with minimal number of states using reverse

So, by the Bzozowski theorem, if A is DFA det(rev(det(rev(A))) would have minimal number of states. And for the most of them work. But for this example, I can't figure out why it doesn't. I have an ...
0
votes
1answer
22 views

Examples of Regular, Context-free and Context-sensitive languages

Assume the languages: $$ a) \, L_1 = \{ w \in \{b,c \}^* | \, w \, \text{contains 'bbc' as substring} \} $$ $$ b)\, L_2 = \{ 1^k 0^m 1^m | k,m \in \mathbb{N} \} $$ $$ c)\,L_3 = \{ w \in {0,1}^* | \,...
1
vote
1answer
48 views

NFA that accepts 0* or 1*

Problem statement: Produce an NFA that accepts the strings 0* and 1*. So 000 and 11 would be accepted, while 101 would not be. I'm a bit concerned about my idea because not all combinations of the ...
0
votes
0answers
16 views

Given a DFA M, formally define an NFA N such that L(N) = {x in L(M) | x = reverse(x)}

The english description of the question is (from my understanding) N accepts all strings that are both palindromic (the same forwards as it is backwards) and accepted by M. After a lot of toil and ...
-1
votes
0answers
29 views

Design a DFA to output Decimal Number

An input alphabet consists of the following symbols ONE, TWO, THREE,....,HUNDRED. Design a DFA that accepts input as the English language representation (e.g., ONE HUNDRED THIRTY FIVE) of any number ...
31
votes
2answers
2k views

Planar regular languages

In my class a student asked whether all finite automata could be drawn without crossing edges (it seems all my examples did). Of course the answer is negative, the obvious automaton for the language $\...
1
vote
1answer
35 views

Prove that a language is bounded if and only if it's finite

Let's assume $L$ is a language. $L$ is bounded if for some natural number $n \in \mathbb N$ applies $|x| ≤ n$, where $|x|$ is a length of a string, with every $x \in L$. Let's also assume that $L$ ...
2
votes
1answer
43 views

Prove: If finite automata M with k states accepts a string with at least k characters, then the language L(M) is infinite

I need to prove that if finite automata $M$ with $k$ states accepts a string with at least $k$ characters, then the language $L(M)$ is infinite. I have no idea where to start. Any suggestions?
0
votes
0answers
17 views

What classifier can recognize differences in two text strings immediately?

I'm playing around with the TextBlob library for python. It has in it a NaiveBayesClassifier as well as a ...
1
vote
1answer
22 views

Example of a locally trivial semigroup

I was having a look at the block product principle for finite monoids. I wanted to see the derivation of LTT = Acom$*$LI, using an example. But I can't come up with a non-trivial example of a monoid ...
0
votes
0answers
24 views

Uncommon case in Arden's lemma $q_{2} = 1q_{2} \cup 0q_{2}$

I'm trying to get the regular expression of an automata but an state has a form that I don't know how to solve, the form on its simplest example is: $$q_{2} = 1q_{2} \cup 0q_{2}$$ What's the ...
2
votes
1answer
25 views

Computing epsilon-closure. What does $E(n) \leftarrow \{n\};$ and $E(p)$ mean?

I'm currently reading "Engineering a Compiler" book. In the chapter that explanes computing epsilon-closure there is listed the following algorithm: But I couldn't understand what does $E(n)$ and $E(...
0
votes
1answer
36 views

Create automata from non regular grammar

I have two grammars: L → ε | aLcLc L → ε | aLcLc | LL This two grammars are equals but the first one is regular, so it produces a regular language and a ...
0
votes
0answers
57 views

How to prove this language is not regular?

I am currently learning Pumping Lemma and found this question. But I am not able to prove it not regular. L = { $0^n$ | n is power of 2}. So, here I considered w = $0^{2^n}$ where n is constant of ...
1
vote
1answer
91 views

Write down a DFA for the regular expression (000* + 111*)* and explain why it cannot have lesser number of states

So, I came up with a DFA for the regular expression. Now for every string described by the regular expression, the DFA accepts it. But in order to ascertain if it's really a DFA for the regex, you ...
0
votes
1answer
27 views

Can you determinize an NFA in PSPACE?

QUESTION Given some NFA $A$, can you simulate the determinization of it (using Subset-Construction for example) while remaining in $PSPACE$? MORE DETAILS I'm asking this as I want to be able to ...
2
votes
2answers
203 views

Proof: There exists an irregular language L such that LLLL is regular

As title. I consider finding a specific L to fulfill the condition stated to prove the statement, however, I have no luck in finding one. A senior gave me a hint that Lagrange's four square theorem ...
0
votes
0answers
27 views

Converting DFA to RE [duplicate]

I have been trying to solve this problem. Convert the DFA to a regular expression. I extracted these following equation. $q_1 = q_2a$ $q_2 = q_1a + (a+b)q_3$ $q_3 = q_1b + q_2a $ Also,the ...
0
votes
0answers
36 views

Testing if a state is in final state

Please excuse my language, I am new to the topic. I am trying to classify/find a class of game that describes games such as chess, tic-tac-toe as a finite state machine. For those games, final ...
0
votes
0answers
30 views

Fastest algorithm that determines whether a given DFA is minimal? [duplicate]

NOTE - I can't find a good answer in the Similar question above ^ Given a DFA, is there a fast algorithm that determines whether it's minimal? I'm looking for an algorithm that works faster than ...
0
votes
1answer
42 views

Number of final states in minimal DFA for $a^*b^*+b^*a^*$ [closed]

How many final states exist in the minimal DFA that accepts the language $a^*b^* + b^*a^*$?
2
votes
2answers
577 views

Why can't DFA's have 0 exiting arrows for some input symbols?

Suppose you are in a middle of computation on a non accepting state and at this point, an input of 0 is rejected by the DFA. But, according to Sipser's formal definition, you must still draw an ...
0
votes
0answers
27 views

why does the pumping lemma want us to only consider the first repitition of states?

In Sipser's Intro to Theory and computation, He writes: I don't understand the constraint on x. Shouldn't it be just y <=p? (Equal bc in the case when machine M runs through all states p) Making ...
2
votes
2answers
32 views

Given an non-deterministic finite automaton, will its determinization always have unreachable states?

Given an NFA that accepts the regular language L, will its equivalent DFA which accepts the same language L always have unreachable states. If it does, why?
1
vote
1answer
259 views

what is the difference between transition function (delta) and extended transition function (delta cap ) in finite automata

my doubt is what is the difference between transition function (delta) and extended transition function (delta cap ) in finite automata ? both of them when started at a state q for a string w will ...
5
votes
4answers
2k views

Are Finite Automata Turing Complete?

Something is Turing Complete if it can be used to simulate any Turing Machine. So, can a Finite Automaton simulate a Turing Machine? On the question Can regular languages be Turing complete? they ...
2
votes
0answers
81 views

Intersection of two deterministic parity automata

Given two deterministic parity automata $A_1=(Q_1,\Sigma,\delta,q_{01},c_1)$ and $A_2=(Q_2,\Sigma,\delta,q_{02},c_2)$ with the finite set of states $Q_i$, the finite alphabet $\Sigma_i$, the ...
1
vote
1answer
24 views

A deterministic FA for $0^*1^*$ is required

A deterministic finite automaton without $\epsilon$ steps for the language $0^*1^*$ is required. Any nice picture ? I have created a NFA for this language which has 2 states $Q_1,Q_2$, both are ...
2
votes
2answers
56 views

Is the language L = {(a,b)* | #a * #b is an odd number} regular?

Is the following language regular? $$\{ w \in \{a, b\}^* |\ \text{the product of the number of $a$'s and the number of $b$'s is an odd number}\} $$ If i'm not mistaken the condition is the same as ...
2
votes
1answer
23 views

Polynomial-time Compute the Number of States resulting from the NFA to DFA (greedy) conversion?

The canonical NFA to DFA conversion, starting with an NFA with $n$ states, can result in a DFA with $2^n$ states. However, in many cases, there are states that are "unnecessary," such as when ...