# 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,728 questions
Filter by
Sorted by
Tagged with
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
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 ...
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 ...
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
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 ...
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 ...
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
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
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 ...
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 ...
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
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 ...
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 ...
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?...
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 ...
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 ...
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 ...
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 ...
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
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$?...
4k views

### Are all DFAs also NFAs?

Are all Deterministic Finite Automatons also Non Deterministic Finite Automatons?
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 ...
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$ ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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?
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 &...
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