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
2 answers
109 views

Create DFA such that every substring of w of length 3 contains two or three 0's with w={0,1}

I am attempting to draw the DFA of this problem but I'm kind of stuck. In another post I saw that the DFA should have 10 states. I'm finding it hard to even understand the question, is the input to ...
1 vote
2 answers
236 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 ...
4 votes
1 answer
139 views

Simultaneous reachability of NFA states

Suppose I have a $n$-state non-deterministic finite automaton $F$ over alphabet $\Sigma$. Let $S(x)$ be the set of states reachable from the starting state by consuming string $x$. I am interested for ...
2 votes
1 answer
12k views

What is the difference between transition function (delta) and extended transition function (delta hat) in finite automata?

What is the difference between transition function delta ($\delta$) and extended transition function delta hat ($\hat{\delta}$) in finite automata? Both of them, when started at a state $q$ for a ...
1 vote
1 answer
60 views

DFA for even concatenation of strings from a language

If I have a deterministic finite automaton (DFA) with a language $W$, and I need to create another DFA that returns all the strings that are a concatenation of an even number of strings in $W$, how ...
0 votes
1 answer
137 views

nfa of the Language L={w belongs to (a,b)*/w starts with aa or ends with aa} with or being not exclusive

I have a question I need to give the NFA of the following language: L={w belongs to (a,b)*/w starts with aa or ends with aa} with or being not exclusive meaning I can have a word that starts with aa ...
0 votes
1 answer
1k 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,...
1 vote
2 answers
7k 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 ...
1 vote
1 answer
22 views

Does there exist terminology to discern NFA states and NFA-transformed-into-DFA state?

I can't find this from surface search in the literature When one observes/simulates NFA after processing several characters, one has to consider both "internal states of NFA" (individual ...
0 votes
1 answer
93 views

Intersection of Infinite Regular Language with CFL

Intersection of any finite regular language with anything( CFL or not CFL) will be finite but what about intersection of infinite regular language with CFL or not CFL. Does the resultant will be ...
0 votes
0 answers
32 views

1 way 2 stack and 2 way 2 stack Pushdown Accepters that accepts L={a^(n^2)|n≥1}

Using a 1 way 2 stack, and a 2 way 2 stack PDA, I want to check if the length of a an input string is strictly a perfect square number. How can I do this in both approaches?
1 vote
1 answer
533 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 ...
0 votes
2 answers
42 views

Why does lexer has O(n) time complexity?

According to my CS knowledge so far, a lexer uses DFA(which takes linear time) for 'each' token type to find the next token, so in the worst case, it should try 'all possible' token types of a ...
0 votes
1 answer
78 views

Explain meaning of states and transitions for DFA that accepts two binary words (a,b) with b = 5a

I was provided with the solution to the language being represented. An example of accepted input would be [001][101]. The DFA that would recognize this language is below. What do the states represent?...
0 votes
2 answers
70 views

How to find prefixes and suffixes for infinite languages? (Automata)

L= {abc} prefix = {epsilon,a,ab,abc} suffix = {epsilon,c,bc,abc} It's easy to find suffixes and prefixes for finite Regular languages. But what will be the ...
0 votes
1 answer
79 views

What could be possible NFA for the RegEx "a?"

I am trying to use the Thompson's method to draw an NFA for a RegEx given by: $(a+b|c?)c$ I am wondering if I should deconstruct the RegEx as - Concatenation of $a+$, $(b|c?)$ together with $c$ OR ...
0 votes
0 answers
62 views

Turing machine for a^n b^m c^n d^m

The state diagram for the initial part of this turing machine given as: Here, we are basically traversing through the input tape, changing occurence of 'a' to X1, and 'c' to X2. After that we go back ...
12 votes
1 answer
7k views

If $L$ is a regular language then so is $\sqrt{L}=\{w:ww\in L\}$

I am interested in proving that $\sqrt{L}=\{w:ww\in L\}$ is regular if $L$ is regular but I don't seem to be getting anywhere. If possible I was hoping for a hint to get me going in the right ...
3 votes
2 answers
2k views

Determining Length of a walk in Nondeterministic Finite Automata with Lambda Transitions

I am learning about CS Theory and specifically Nondeterministic Finite Automata (NFA) right now. In my book I came across a section of text that discussed a way to determine the length of a walk ...
1 vote
3 answers
2k views

Length of distinguishing string for a DFA

Is it possible for a $DFA$ which has $n$ states that, there exists two distinguishable states $p, q$ such that there exists a distinquishing string between $p$ and $q$ whose length is greater than $n$?...
6 votes
2 answers
4k views

Are all DFAs also NFAs?

Are all Deterministic Finite Automatons also Non Deterministic Finite Automatons?
0 votes
1 answer
605 views

Can we skip an input in push down automata

Hi here I'm giving a language L3={0^m 1^(n ) 2^m | m,n ∈ N} I designed this stack machine in order to accept this given language. Here I'm skipping 1 (no matter how many 1s are there) . Is it ok to ...
0 votes
0 answers
27 views

What is the minimum length word accepted by the product of these simple loop automata?

Let $A_{n} = (aa|aaa|aaaa|\dots |a^{n-2})(a^{n})^* $ where $n \geq 4$ is some natural,and $A_2 = (a^2)^*, A_3 = (a^3)^*$. Clearly every transition is thus labeled by an $a$. From now on let $A_n$ ...
2 votes
1 answer
66 views

What is the Minimum length of a string that is accepted by a DFA that shows that the language accepted by that DFA is infinite?

What is the minimum length of a string that is accepted by a DFA, shows that the language accepted by that DFA is infinite? I checked this post How to determine if an automata (DFA) accepts an ...
0 votes
1 answer
61 views

Construct a regular grammar that produces all possible strings of $\Sigma = \{a,b\}$ that do not contain substring 'abba'

I'm really stuck here and do not know what to do. So far, I've constructed a DFA and a regular expression that produces the aforementioned set of strings. Namely, the DFA looks like: After a lot of ...
7 votes
1 answer
289 views

A Turing machine with each cell accessed at most $10$ times has an equivalent NFA

I am confused by the following claim: Let $T$ be a (decider, single-tape) Turing machine with the property that for every input, every cell on its tape is accessed at most $10$ times. Then there is a ...
3 votes
1 answer
181 views

NP completeness of deciding whether a set of examples, consisting of strings and states, has a corresponding DFA?

I'm working on a textbook problem, 7.36 in Sipser 3rd edition. It claims that if we are given an integer $N$ and set of pairs $(s_i, q_i)$, where $s_i$ are binary strings and $q_i$ are states (we are ...
0 votes
0 answers
43 views

After converting a CFG to a PDA, what is an example input string to the PDA?

For example, the following CFG: S$\rightarrow$aSb|$\epsilon$ A valid string within the language described by the CFG would be, e.g., "aabb". The converted PDA has the following form: The ...
0 votes
0 answers
40 views

Binary combinatorics with rank

I am looking at finding acceptable binary values with maximum 2 consecutive 1s and 0s, from a range of maximum 6 bits (2^6 values). Also, I want to rank and unrank these subset of values (in ...
0 votes
0 answers
27 views

DFA for "K" bit value with max "n" consecutive "0"s and "1"s

I had posted earlier a question regarding ranking max "n" consecutive "0"s and "1"s in a "K"-bit string - Order in a subset I got clarification regarding how ...
0 votes
1 answer
71 views

Question about remainder in automata construction that checks divisibility

I'm trying to understand de construction of a DFA from the book "Introduction to Automata Theory, Languages, and Computation by John Hopcroft and Jeffrey Ullman 1st ed" It says: Where it ...
0 votes
0 answers
60 views

Minimum number of states in a DFA

Consider the language L given by the regular expression (a + b )*b(a + b) over the alphabet {a, b} . The smallest number of states needed in a deterministic finite-state automaton (DFA) accepting L is ...
0 votes
0 answers
48 views

How to convert a NFA to alternating finite automata AFA?

I am trying to construct an AFA from a NFA, how do I know if a state of NFA becoms existential or universal in the AFA?
0 votes
1 answer
81 views

Simple description of the LR(0) table generator algorithm?

I have just implemented a parser on the relational database. Parsing is done with recursive query. Note: one commenter was misled by the word "recursive" before "query" to think &...
2 votes
1 answer
202 views

Is it possible to create a NFA that accepts only n*"a" or n*"b" inputs?

I'd like to create a NFA that accepts only inputs like "aaaaa";"a";"bb";"bbb", but not like "aab";"aabaa". Is the even possible? As far as I ...
1 vote
2 answers
82 views

Is my regular expression and finite automata diagram for this state table correct?

So i have some theory of computer science homework and I'm struggling with this question currently. I am given the following automaton: $Q = \{q_0,q_1\}$. $\Sigma = \{a,b\}$. $q_0 = q_0$. $F = \{q_0\}...
4 votes
1 answer
69 views

Translating non-deterministic finite automata with counters to deterministic ones

I know there are algorithms for translating regular NFAs into their corresponding DFAs. Can these algorithms be applied to automata that employ transitions involving counters in a straightforward way, ...
32 votes
4 answers
7k views

How to simulate backreferences, lookaheads, and lookbehinds in finite state automata?

I created a simple regular expression lexer and parser to take a regular expression and generate its parse tree. Creating a non-deterministic finite state automaton from this parse tree is relatively ...
0 votes
1 answer
337 views

Conversion of epsilon NFA to DFA, handling epsilon transitions

I am reading Michael Sipser's "Introduction to theory of computation" 3rd edition, page 55 - 56, the topic "equivalence of DFAs and NFAs" Case 0: Michael Sipser asks us to handle ...
0 votes
1 answer
131 views

How to build a DFA that recognizes a language

I have been given the following problem and was wondering if my solution is correct (taken from the textbook exercise in the book Introduction to the Theory of Computation by Martin Sipser): Build a ...
2 votes
0 answers
34 views

Let $∑$ be an alphabet. Is the set of all DFAs over $∑$ countable?

Let $∑$ be an alphabet. Is the set of all DFAs over $∑$ countable? I know the set of all regular languages is countable, however, it is impossible to build an injection from the DFAs to the regular ...
1 vote
1 answer
195 views

Pumping Lemma $A = \{0^n1^n \mid n \geq0\}$. Prove $A$ is not regular

Question : Are my Justifications Correct? Pumping Lemma $A = \{0^n1^n \mid n \geq 0\}$. Prove $A$ is not regular : Suppose $S = 0^p1^p$ and $p = 3$. Therefore, $S = 000111$. Breaking $S$ into $xyz$ ...
0 votes
2 answers
36 views

Linked Finite State Machine

Let us assume, we have a FSM (to be precise, an epsilon-NFA) in which I've got redundant structures. I am looking for a framework that allows to factor out the redundant part into some kind of ...
0 votes
1 answer
24 views

Equivalence of echo state networks and DFAs/NFAs

Echo state networks are theoretically equivalent to DFAs/NFAs, but how would you use an ESN to parse a regular language? Would you just feed many different input strings, some from the language and ...
0 votes
1 answer
122 views

Copy operation in under 9 states?

There is a long row of cells. Each cell contains 0 or 1. A machine is positioned immediately to the right of a series of uninterrupted 1’s followed by an uninterrupted series of 0’s. In the following ...
0 votes
1 answer
55 views

What strings are accepted by the described DFA?

Could someone clarify what strings are accepted by the described DFA? Draw a DFA for the set of all strings with two consecutive 0’s followed by two consecutive 1’s over Ʃ= {0,1}
0 votes
0 answers
63 views

How to convert NFA with multiple start states to NFA with single start state without epsilon transition?

I can easily convert NFA with multiple start states to NFA with single start state with epsilon transition. But I want to know how can I do so without epsilon transition Here's my idea Suppose s1 and ...
0 votes
3 answers
8k views

Is (a+b)* and (ab)* same in finite automata?

Regular language of (a+b)* and (ab)* are: (a+b)* = { ε, a, b, aa , ab , bb , ba, aaa, ...} (ab)* = { ε, a, b, aa, ab, ba, bb, aaa, ... } I am new to Finite automata and this simple notion is ...
0 votes
1 answer
63 views

Simplifying regex expression (L+M*)*

To simplify it, it seems that we can do $(L+M^*)^* = (L+M)^*$, but I also need to prove it.$(L+M)^* ⊆ (L+M^*)^*$ seems straight forward. However, $(L+M^*)^* ⊆ (L+M)^*$ is what I couldn't figure out. ...
3 votes
1 answer
2k views

Are DFAs unique?

For a given regular is expression, once we construct a deterministic finite automaton: is that automaton unique for that expression? In a sense, that no other DFA (different number of vertices or ...

1
2 3 4 5
35