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
0answers
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 ...
-1
votes
0answers
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\}$, ...
1
vote
1answer
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 ...
1
vote
1answer
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. ...
1
vote
2answers
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 ...
0
votes
1answer
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$ ...
-3
votes
0answers
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.
2
votes
1answer
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 ...
1
vote
0answers
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 ...
0
votes
1answer
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 ...
0
votes
1answer
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 ...
0
votes
0answers
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 ...
0
votes
1answer
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 ...
-2
votes
0answers
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\}^*\}$
1
vote
1answer
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 ...
1
vote
1answer
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 ...
1
vote
1answer
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 ...
0
votes
1answer
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 ...
0
votes
1answer
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, ...
1
vote
1answer
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 ...
0
votes
1answer
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,...
0
votes
1answer
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. ...
10
votes
1answer
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 ...
1
vote
0answers
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) ...
0
votes
1answer
23 views

What does c represent in Sipser's explanation of the modified post correspondence problem Introduction to the Theory of Computation book?

I'm supposed to perform actions corresponding to the different steps in Sipser's explanation of the Modified Post Correspondence Problem, but I'm not sure I understand the third step. The part I'm ...
0
votes
1answer
14 views

What is the meaning of Sub_tm in this context?

Im working on a problem for a homework assignment in finite automata, but I'm having trouble conceptually grasping the problem in the first place. Prove that the following is undecidable: $SUB_{TM} = \...
6
votes
2answers
1k views

Proof that for 2n nodes of +1 and -1 position doesn't count

I'm having a hard time understanding how to solve this problem for my Computer Science 101 class. On a circle there are $2n$ nodes. $n$ out of these hold -1 power and $n$ hold +1 power. Say we play a ...
1
vote
1answer
261 views

Converting DFA to Regular Expression Using State Removal

I'm trying to convert the following NFA to a regular expression. I've attached my work below and end up with the expression $aa^*bb^*$. As far as I can tell, this doesn't seem correct but I've been ...
1
vote
1answer
104 views

How do you create a sentential form in a given grammar?

I am given the following grammar: $$S ::= aBS| abT |a$$ $$T::= d | dT$$$$B ::= da | ϵ | S$$ I need to decide whether $aBaabda$ can be produced in the given grammar. I am unsure how the grammar can ...
-1
votes
1answer
51 views

Prove $(aa^*bb^*)^*=ϵ+a(a+b)^*b$ using regex laws

I tried to prove this by starting at RHS: $$ϵ+a(a+b)^*b = ϵ+a(a^*b^*)^*b$$ But I dont know how to convert $(a^*b^*)^*$ to something else that will be helpful. Any ideas?
0
votes
1answer
212 views

How to construct an NFA Ai for the given Regular property P1 and P2?

Let AP = {a; b; c}. Consider the following regular safety properties: (a) P1: If a becomes valid, afterwards b stays valid ad infinitum or until c holds. (b) P2: Between two neighbouring occurrences ...
1
vote
0answers
58 views

Is there a complexity measure on regular grammars connected to the descriptional complexity of the DFAs?

This question is directed at DFAs/NFAs and regular languages and regular grammars. Define the "descriptional complexity" of a language as the size complexity of the family of DFAs that ...
1
vote
1answer
21 views

DFA minimazation (dead state)

I was trying to minimize given DFA: a b -> 1 4 2 F 2 1 1 3 1 4 F 4 1 1 I've watched few videos about solving this problem and decided to use the equivalance method. While doing it I've come ...
0
votes
1answer
30 views

How do we decide whether or not to accept $\epsilon$ in dfa?

Can I exclude $\epsilon$? Will that make a difference. This is really confusing me. It seems everything could contain $\epsilon$. Is there some way of thinking to realize this contains $\epsilon$ or ...
2
votes
0answers
19 views

How to build a minimal string matching DFA with limited memory?

I am working on finite state machine pruning, a problem that requires me to build finite state machines (in the manner of the Aho Corasic algorithm) to match an evolving input string against a set of ...
2
votes
1answer
30 views

Convert a dfa to rule for a asterisk case

Here is a simple but very common grammar rule case in EBNF format, the Statements is a none terminal symbol and Statement is ...
3
votes
4answers
168 views

Are there any programming languages that support state machines in their standard library?

State machines are a fundamental computer science concept and in many senarios they are the simplest way to implement a process or program. However, most programming languages don't support them ...
-1
votes
1answer
61 views

Prove language is not Turing-recognizable using contradiction

Show that the language L = {<M>| M is a TM and does not accept <M>} is not Turing-recognizable. Note: Prove by contradiction. No need for reduction. This is the problem I am trying to ...
2
votes
3answers
90 views

PDA for a language where the second part is not the reverse of the first part

I came across an exercise for constructing a PDA for the following language: $$L = \{ncm \mid n,m\in\{a,b\}^* \text{ and } n \ne m^R\}.$$ Where $L \subseteq ({a,b,c})^*$ So $n$ and $m$ are both a ...
0
votes
1answer
56 views

How do I create a finite state automata for addition in ternary system?

I've been scratching my head with this one for a few hours now, but am feeling to stupid to comprehend how it is to be done. I can't understand the way even the state table should be built for this ...
0
votes
2answers
48 views

When you convert epsilon NFA to NFA, how do you decide the final states of resultant NFA?

The question is-: THIS is the transition table for NFA-: Final result as shown in youtube video. https://www.youtube.com/watch?v=GjLiXk0imi0&list=PLENQMW_c1dimRCKF3bjUqHaH8dvJkapSw&index=49 ...
4
votes
3answers
578 views

Are there algorithms to exactly minimize NFAs which are sometimes efficient?

I'm doing some research with NFAs, and I'm wondering there are algorithms which quasi-efficiently minimize them. I realize that this problem is $PSPACE$ hard, so I'm not looking for a polynomial time ...
-2
votes
1answer
35 views

What does DFA that accepts at least 1 a or at least 1 b mean?

What are the language accepted by this DFA? The truth table of OR-: But I am unable to deduct what this dfa will accept? Say-: P=at least 1 a Q=at least 1 b So DFA should accept both ab. Or in ...
0
votes
1answer
33 views

Regular expression for set of all strings containing no 3 consecutive 0s?

The answer is $1^*01^*01^*+1^*(0+00+\in)1^*$ If I had to rephrase my question, it would be how to approach regular expression problems? Is it all about practice? How do I understand what the regular ...
1
vote
2answers
35 views

NFA has power to be in several states at once implies NFA has ability to guess about its input. How?

I agree that NFA has power to be in several states at once. It probably means that on same input, NFA can be on multiple states. But what I can't understand is how can we conclude from this that "...
-3
votes
1answer
52 views

Design a DFA that accepts language L={ x in (0,1)* | the third bit from x from its right end is 1}

this is very confusing question. I am having no idea to solve it, can you please guide me here?
0
votes
0answers
28 views

conversion of epsilon NFA to NFA

I was given below task: Eliminate Epsilon-transitions in below automata My solution: Is it correct that stage 1 is actually one of the final stages? How does it work in given example? We have ...
1
vote
1answer
33 views

conversion of NFA to DFA (omitted states)

I've been given following task: Determine the following nondeterministic automaton (omit unreachable states, if they appear during construction) My solution to this: Would like to ask for a ...
0
votes
1answer
13 views

Problems with simulating NFA with DFA

I have this NFA: I want to simulate it with a DFA, thus I have the states {1}, {2}, {3}, {1,2}, {1,3}, {2,3} and {1,2,3}. Usually I look at every state and find out in which state I could end up when ...
0
votes
1answer
44 views

Need help with constructing a DFA

I am trying to construct the DFA that accepts the following language $$ L_2 := \left\{ w \in \{a,b\}^* \mid \#a(w) \text{ is divisible by } 3 \text{ and } \texttt{babbab} \text{is a substring of } w \...

1
2 3 4 5
31