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,532 questions
Filter by
Sorted by
Tagged with
6 views

What is the difference between these 4 Finite Automatons?

I am a Uni student and am a little bit confused.. because I was wondering what the differences are between FA1 and FA2 -> as well as the differences between FA3 and FA4. Because to me they all look ...
19 views

Counter automata for languages with conditions on the numbers of 0s and 1s [closed]

A counter automation is a PDA with just two stack variables, $A$ and $Z$, for which the string on the stack is always of the form $A^n Z$ for some $n≥0$. For some CFLs, such as $\{0^i 1^i \mid i≥0\}$, ...
93 views

Create a Deterministic Finite Automaton for a regular expression

I want to create a finite state machine that accepts the following language: $$L=\{w\in\{a,b\}^* | w \text{ contains abb but not on the first position}\}$$ So I began by writing a regular expression ...
40 views

Describing the language of this Automaton

I am trying to describe the above automaton in English. The pattern that I can see is that it accepts any input that starts with $1$ or $0$ with an exact one occurrence of $00$ and ends with 1 or 10. ...
58 views

Is it accurate to contrast a Turing machine with finite automata by claiming the former is stateful and the latter is pure?

Recently, I was having a debate with a friend about what it would mean to create a machine that ZKSnarks (proves) itself. I tossed the word pure machine out there while describing what I hypothesized ...
205 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$ ...
23 views

Conversation from Mealey machine to moore machine

I want to understand the conversion from Mealey machine to moore machine with an example. How we derive the states.
222 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 ...
40 views

Is regex with lookaround still regular?

It is well known that "regex" with back-reference is not a regular expression anymore. For instance, (.*)\1 matches any string repeated twice. However, is ...
36 views

How to create a DFA that accepts strings that are multiples of a number?

I particularly have a problem creating DFAs for multiples of larger numbers like 10, 11 ,12 etc. but I can create simple ones like 1, 2, 3 etc. Even more so, I have a problem creating a minimized DFA ...
55 views

Size of minimal DFA

Assume a given NFA for a regular language with $n$ states. It is clear that determinizing it may result in an DFA with $\Omega(2^n)$ states. However, the minimization might decrease the number of ...
16 views

Could I have used PL directly on this language instead of proving it the way I did? [duplicate]

In an exercise I'm trying to solve I have to say whether a language is regular or not. One of the languages is $L_1=\{0^i1^j \mid i,j \geq 1\text{ and } i\neq j\}$. I have already solved this by ...
19 views

Which z should I pick?

I'm currently trying to show that the language $L_2=\{0^n \text{ } | \text{ } n=2^k, k\geq 0\}$ is not regular by using the Pumping Lemma (at least I think it is not regular, because I couldn't find ...
29 views

Is $\{ww^Ra^{|w|}\mid w\in\{a,b\}^*\}$ context-Free? [duplicate]

How can I prove that this language is context free and construct a pda recognizing it? $L = \{ww^Ra^{|w|}\mid w\in\{a,b\}^*\}$
30 views

What is the difference between these 2 dfas for binary strings ending with 00?

The first one is from unreputed youtuber whereas second one is from reputed university called adiuni course of theory of computation. Now I know what that second figure means, it means it also accepts ...
41 views

epsilon-NFA to DFA conversion - What will be the final states and do we need to create empty state in DFA?

Source of this question and problem: https://www.javatpoint.com/automata-conversion-from-nfa-with-null-to-dfa This is the question: So in this figure there are my 1 confusion-: Don't we need a empty ...
31 views

Problem with Understanding Pumping Lemma

I'm trying to solve this exercise that asks to determine whether a language is regular or not. Following the flow of the course I figured that the exercise is a test for Pumping Lemma application. But ...
60 views

Is this FA really equivalent to the given regular expression?

From the picture, the automata can accept $(\text L|\text D)^*$ following say $\_\text L\text D$, but in the formula above $(\text L|\text D)^*$ can't follow the $\_\text L\text D$. So the Automata ...
33 views

DFA for {w|w contains a substring of length at most 5 that has at least three 1's}

I have thought about this problem, but cannot come up with a convincing answer since I think this problem has too many states too consider. The accepting states can be length 5 substring and 3 1's, ...
119 views

Meaning of $a\lor b \to b' \lor c'$

So I have done part a) but I have no clue what I am supposed to do for part b), I have been trying for days to wrap my head around and even asked my fellow course mates, none of which seem to know ...
865 views

Determine if an NFA accepts infinite language in polynomial time

Question Statement: Given a NFA $N$, design an algorithm that runs in polynomial time such that it determines if $L(N)$ is infinite. (Note that converting NFA to DFA is exponential time). For any DFA,...
65 views

How do I apply the Pumping Lemma to prove that this language is not regular?

I am trying to teach myself Automata theory. I have hard time with the Pumping Lemma, so I am trying to work through examples. I stumbled upon this example, but it doesn't have steps how to solve it. ...
483 views

What is the correct way to draw NFA of RE (a|b|c)?

We were assigned to draw NFA for regular expression a|b|c, so like any one I draw this But my professor told me it is wrong, the correct way is So, I checked it ...
14 views

Design a two-tape deterministic Turing machine M that recognizes the language L3= {x#(0^k) #y : x, y ∈ {0, 1}* , x = y ∧ |x| = k}

I'm having a hard time trying to write a two tape Turing machine I wanted to first think Oh all I'd have to do is scan from left-to-right till I find the strings that matches the accepted strings) ...