Skip to main content
OverflowAI is here! AI power for your Stack Overflow for Teams knowledge community. Learn more

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
4 answers
69 views

Proof that the mind/brain is not a finite state machine by recognizing an unrecognizable language?

Some people believe the human mind is a finite state machine, making references to the Bekenstein bound. I've read that Turing himself imagined the human as FSM with unbounded paper to construct the ...
JobHunter69's user avatar
0 votes
1 answer
23 views

Is $L = \{\sigma_1 u \sigma_2 v \sigma_3 \mid (\sigma_1, \sigma_2, \sigma_3 \in \Sigma, u, v \in \Sigma^*, |u| = |v|) and ...$ regular

The question asks to determine if any of the following languages above $\Sigma=\left \{ 0,1 \right \}$ is regular. The languages are: $L_1=\left \{ \sigma_1u\sigma_2v\sigma_3:\begin{matrix} \sigma_1,\...
Daniel's user avatar
  • 69
0 votes
1 answer
29 views

Decide if some DFA is accepted

Given Some(DFA) = {|A is a DFA and L(A) is not empty and L(A) is not equal to Σ^(*)} Show Some(DFA) is decidable. I produced the following answer and wanted to check if I am correct T="On input ...
keth's user avatar
  • 1
4 votes
1 answer
268 views

Do multi-acceptance/multi-language automata exist in literature?

A multi-acceptance deterministic finite state automaton is a tuple $(Q,\Sigma,\delta,q_0,T,f)$ where $Q$, $\Sigma$, $\delta: Q \times \Sigma \to Q$, and $q_0 \in Q$ are defined in the standard way of ...
matteo_c's user avatar
  • 173
1 vote
0 answers
32 views

Is it possible to construct a mealy/moore deterministic machine which gives an output (say x) for termination type languages?

As far as I know, Mealy and Moore machine are transducing machines and not language acceptors. So, can a Mealy/Moore machine, satisfying their very definitions, be made for languages which deal with ...
Arsenic's user avatar
  • 111
1 vote
1 answer
60 views

Trying to understand better the solution for $L \ regular \to L'=\left \{ xy^{R}z : xyz\in L\ , x,y,z\in\Sigma^{*} \right \} \ regular$

In this post: For a regular language $L$, is $\{xy^Rz:xyz\in L\}$ regular? @Hendrik Jan have give a really good answer but I'm failing to understand it. I have looked at $L=\left \{ abc \right \}$ in ...
Daniel's user avatar
  • 69
2 votes
1 answer
128 views

Efficiently transforming non-recursive CFG into an NFA

It should be possible to rewrite a non-recursive CFG [1] as an acyclic NFA, since non-recursive CFGs represent finite languages (and thus regular a fortiori). Is there an explicit algorithm to rewrite ...
breandan's user avatar
1 vote
1 answer
47 views

Searching for small finite state automata

Suppose I am given a finite state automaton A and a number n which should be thought of as much smaller than the number of states of A. Is there a good algorithm to find all (deterministic) finite ...
Alex Wright's user avatar
0 votes
1 answer
58 views

NFA for $L = \{\sigma_1 u \sigma_2 v \sigma_3 \mid (\sigma_1, \sigma_2, \sigma_3 \in \Sigma, u, v \in \Sigma^*, |u| = |v|) and ...$

The question asks to write a NFA for the following language $L$ above $\Sigma = \left \{0,1 \right \}$. $L = \{\sigma_1 u \sigma_2 v \sigma_3 \mid (\sigma_1, \sigma_2, \sigma_3 \in \Sigma, u, v \in \...
Daniel's user avatar
  • 69
0 votes
1 answer
60 views

Regex for $L = \{ w \mid w \in \Sigma^* \text{ and each substring } u \text{ of } w \text{ where } |u| = 4 \text{ contains the character } 0 \}$

The question asks to write a regex to the following language $L$ above $\Sigma = \left \{0,1 \right \}$. $L = \{ w \mid w \in \Sigma^* \text{ and each substring } u \text{ of } w \text{ where } |u| = ...
Daniel's user avatar
  • 69
0 votes
1 answer
29 views

NFA for a regular expression without $\epsilon$-transitions

I think I know how to convert a regular expression to NFA without requiring epsilon transitions, but I'm not sure if I'm right (I'm just using common sense to be honest, no particular algorithm in my ...
Acad's user avatar
  • 101
2 votes
1 answer
112 views

Is matching pairs sufficient?

Book PDF: https://vishub.org/officedocs/13770.pdf Pg 253 of book This is a snapshot from Dexter C. Kozen - Automata and Computability, Lecture-35, Undecidable problems about CFLs. My question here is ...
PranksterSabeleye's user avatar
1 vote
1 answer
42 views

Constructing a DFA that accepts the set of binary strings with an even length and an odd number of 1s

For this problem, I decided to tackle it by getting the intersection of the DFA that accepts binary strings of an even length and the DFA that accepts binary strings with an odd number of 1s (as seen ...
picato's user avatar
  • 13
0 votes
1 answer
32 views

Constructing a DFA that accepts the set of all binary strings that contain substrings "01" or "10"

I'm having trouble designing a DFA that accepts substrings of both 01 or 10. So far, I have constructed separate DFAs that accept the substrings "01" and "10" respectively. What I'...
picato's user avatar
  • 13
2 votes
0 answers
44 views

Finite state automaton

Recently, I have been trying to understand Kitaev's textbook Classical and Quantum Computation, in which he defines a (finite-state) automaton as a function $D:Q\times A'\to Q\times A''$ where $Q$ is ...
Andrew Yuan's user avatar
1 vote
2 answers
69 views

Finding the Smallest Language Class containing a given language definition

Given two regular languages L1 and L2 over alphabet Σ, we define the operator RQ(L1, L2) = {w | there exists a word v in L2 such that wv is in L1}. The task is to determine the smallest language class ...
Oh No's user avatar
  • 11
0 votes
0 answers
49 views

DFA for $\{s\mid ss\in L(A)\}$ [duplicate]

I've started learning automata recently, and am struggling to figure out how to find a finite automaton that satisfies the following: Given DFA $A_1 = (Q, \Sigma, \delta, q_0, F)$, find a finite ...
Daniel's user avatar
  • 1
3 votes
2 answers
135 views

in NFA is every state itself contained in set generated by transition function when considering epsilon transition from that state?

in $\epsilon$-NFA (NFAs involving $\epsilon$ transitions) when we have $\epsilon$ transitions, I understand it as where can we go if we don't read any symbol from the input tape, then I think every ...
math boy's user avatar
  • 359
0 votes
1 answer
18 views

What is the set FirstHalves B? You can simply write out the set explicitly, enumerating the first four values

For any set of strings A, define the set FirstHalves A = {x∣∃y such that len(y) = len(x) and xy in A }. For example, FirstHalves {01, 111, 1010, 001101, 1011} = {0, 10, 001}, ie the first halves of ...
Firdaus Shallo's user avatar
1 vote
0 answers
47 views

A proof that $a^n b^m $ for $n\neq m$ is not regular by using the pumping lemma

I am looking at $L=\{a^nb^m |n\neq m \}$. I would like to prove that $L$ is not regular. This can easily done by assuming it is regular and looking at $\overline L$, or by using other theorems. ...
Eric_'s user avatar
  • 445
1 vote
2 answers
88 views

Subset Relations Between CFGs and Their Languages

Is it possible for there to exist two context-free grammars where the set of rules of the first is a proper subset of the set of rules of the second, yet the language generated by the second grammar ...
Mocak's user avatar
  • 15
1 vote
1 answer
79 views

Draw a finite automation for {w ∈ Σ ∗ | w does not contain the substring 10}

So I am trying to draw a finite automation that has no limits on the length, but cannot have the substring of 10 I created a DFA that could satisfy this requirement,...
cool cat's user avatar
-1 votes
1 answer
64 views

What is the regular language for L = {w | w has even length, and starts and ends with the same symbol}?

I originally thought it was 0(01)*(01)0 U 1(01)(01)1 where: two versions: one that starts and ends with 0, the other that starts and ends with 1 connected by plus, which does not mean union of both ...
cool cat's user avatar
-3 votes
2 answers
46 views

A more concise Finite Automata for 10 substring?

I am learning about finite automata and trying to create a machine that matches {w ∈ Σ∗| w does not contain the substring 10} I created a DFA where it either starts ...
user168855's user avatar
1 vote
2 answers
68 views

Shortest regular expression possible

The question asks to write the shortest regular expression possible to the following automaton: I see only one way to tackle the problem: Use one of the methods mentioned here How to convert finite ...
Daniel's user avatar
  • 69
-3 votes
1 answer
35 views

How to convert the following from NFA with ε-moves to DFA?

Can you provide the transition table along with the solution for better understanding?
Korra's user avatar
  • 1
-1 votes
1 answer
50 views

Construct a regular expression for strings over the alphabet {a, b, c} that don’t contain the contiguous substring "baa"

I want to construct a regular expression for strings over the alphabet {a, b, c} that don’t contain the contiguous substring "baa". I tried to follow the same procedure as in all the words ...
Nolen's user avatar
  • 1
0 votes
2 answers
100 views

regular expression for $\{w\in \{a,b\}^*\mid |w|_a \mod 2 = 0\}\setminus \Sigma^*aab\Sigma^*$

The question asks to write down a regular expression $r$ indicating the language of all the words above $\Sigma = \{a, b\}$ , in which the number of $a$ is even and there is no sub-word $aab$ in them. ...
Daniel's user avatar
  • 69
1 vote
2 answers
81 views

Resources on Moore and Mealy Machines

I was studying about Moore and Mealy machines but having hard time connecting with them because 1) they are different from typical normal machines.what is the need of "output" and 2) My text ...
hxdshell's user avatar
0 votes
1 answer
66 views

DFA that accepts strings ending with an even number of 1 in the last three characters ("000","110","101","011")

I need to design a binary DFA to accept strings where the last three characters read are either "000", "110", "101" or "011". My brutal solution is: I need ...
Green's user avatar
  • 11
2 votes
1 answer
78 views

Create NFA where |w|_a is divisible by 2 or |w|_b is divisible by 3

I have to create an NFA $\mathcal{A}$ that accepts the language $L = \{w \in \Sigma^* \ | \ |w|_a \ \text{is divisible by 2 or} \ |w|_b \ \text{is divisible by 3} \}$ So the NFA only accepts words ...
Ben's user avatar
  • 21
1 vote
1 answer
64 views

How to show L is non-regular without pumping lemma?

$L=\{(ab)^n : n\text{ is a natural number apart from }6\}$, I want to show L is non-regular by finding an infinite set of L-distinguishable words. Could you help me?
osdinuto's user avatar
0 votes
1 answer
16 views

Hardwiring input in DFAs and PDAs

A Turing Machine can be converted into a Turing Machine that has a specific input coded into it's description. This Turing Machine can then be run on empty input. Can we do the same for PDAs or DFAs? ...
Zee's user avatar
  • 243
4 votes
0 answers
121 views

Constructing worst case for L* by D.Angluin

I'm working on constructing deterministic finite automata (DFAs) with a specific learning complexity when using the L* algorithm developed by Dana Angluin. My goal is to create a DFA of size ( n ) ...
Coping Forever's user avatar
3 votes
1 answer
170 views

Difference between product automaton vs. NFA with epsilon transitions

Let $L_1, L_2$ be regular languages. You can proof with a product automaton that $L_1\cup L_2$ is also regular. But you can also construct a NFA. Since $L_1, L_2$ are regular, they also have an NFA ...
identicon's user avatar
2 votes
1 answer
272 views

Pumping Lemma Applied to 3 Variables

Prove That the Language $L_1 = \{0^i1^j0^k | i < j\ or\ i > k\}$ is not regular using the pumping lemma. I am not sure how to begin with this I ended up using the string: $0^p1^{p+1}0^{p+1}$ S = ...
Juan's user avatar
  • 23
1 vote
1 answer
59 views

Provide a 2-state DFA for L={a}∗{b}∗ , the set of words of the form aa⋯abb⋯b

I'm kinda confused on how to construct this DFA. I'm trying but keep running into the problem of reading an a after the b's or what to do if starting with a 'b'.
user167205's user avatar
0 votes
1 answer
35 views

Trouble proving this is regular

I'm taking an automata class and one of the examples is showing this is regular. My initial thought was to make a DFA to show it is but i'm a bit confused on what a DFA with a standard 5 tuple would ...
user167205's user avatar
1 vote
1 answer
64 views

Why can't we prove closure under concatenation using DFA?

I can't understand why do we have to use NFA to prove that concatenation operation is closed. According to sisper's book it says that we can't determine where to split the string, i.e. where to ...
hxdshell's user avatar
2 votes
2 answers
2k views

Converting Regex to DFA

People I know said that converting a Regex to DFA is just a "matter of judgement" (I do not believe them, there has to be a more systematic approach). Is there a simple/intuitive, yet ...
einzigartigerhummer's user avatar
2 votes
1 answer
40 views

What does the language of DFA of LR itemsets represent?

As we know, if we want to make a $LR(0)$ (say) parsing table for a context free grammar (CFG), we prepare the $LR(0)$ itemsets with $.$ (dot) in RHS of the CFG production. With this $.$ we keep track ...
Ajit Kumar's user avatar
0 votes
1 answer
177 views

NFA for the language that accepts binary strings ending with 00

This is the question: 1.7. Give state diagrams of NFAs with the specified number of states recognizing each of the following languages. In all parts, the alphabet is {0,1}. a. The language {w| w ...
Amir's user avatar
  • 3
0 votes
0 answers
66 views

How to work thompson's construction algorithm?

Could someone explain to me, through an example, how the McNaughton–Yamada–Thompson algorithm works in a way that I can understand? Thank you in advance for your helpful response!
ProgrammerGnome's user avatar
-1 votes
1 answer
43 views

Is this correct Context free grammar(CFG) for these two languages?

Question 1: L = { 0^n 1^n | n > 0 } My answer = S -> 0 S 1 | 10 Question 2: L = { 101^n0^2n | n > 0 } My answer = S -> 101 S 00 | 100 Can anyone correct this if there is any issue with ...
Elijah's user avatar
  • 1
1 vote
0 answers
28 views

In regular language inference, how is the observation table kept consistent?

I am trying to understand the background literature on regular language inference in the TTT paper ("The TTT Algorithm: A Redundancy-Free Approach to Active Automata Learning" by Isberner, ...
Rahul Gopinath's user avatar
1 vote
1 answer
120 views

How to construct complement of NFA universality?

Given an input NFA, can one construct an NFA that is universal (that is, accepts all its inputs) if and only if, the input NFA isn't universal? I tried to use the fact that NFA-universality is PSPACE-...
NooneAtAll3's user avatar
2 votes
1 answer
102 views

Applications of ω-automaton in engineering

Finite automaton is a well-known topic which finds applications in software engineering (e.g. pattern matching or regular expressions in general). ω-automaton are another kind of automaton, defined ...
Weier's user avatar
  • 231
0 votes
1 answer
56 views

Determining the language of a DFA

I've tried quite a large amount of examples, starting from 1 bit all the way up to 5 bits yet I couldn't put my finger on any recurring pattern of words that are accepted. the DFA is as such: The ...
Aishgadol's user avatar
  • 355
1 vote
1 answer
251 views

How to build a deterministic or non deterministic finite automat for a language

$L_1$ and $L_2$ are two languages that have a finite deterministic automaton. $Σ = \{0,1\}$ for the two languages. Let $L=\{x∈L_1\mid \text{there exists } y∈L_2,\text{such that } \#_0(x)=\#_0(y)\}$, ...
ella's user avatar
  • 11
0 votes
1 answer
63 views

Proving that the intersection of two languages is regular or not?

Let $B$ and $C$ be two languages on $A = \{a,b\}$: $B = \{ w \mid w \text{ has the same number of }a\text{ and }b\text{ symbols}\}$ $C = \{ a^n b^m \mid n,m \ge 0\}$ Describe $B \cap C$ and determine ...
Luca 's user avatar
  • 63

1
2 3 4 5
36