# 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,674 questions
Filter by
Sorted by
Tagged with
69 views

### Regex where all strings containing an even number of 0's:

Question is to construct a regex where all strings containing an even number of 0's: By constructing DFA graphically, it is $$(1^*+01^*0)^*$$ But it is also $$1^*(01^*01^*)^*$$ Can we prove that they ...
• 55
9 views

### RE to NFA conversion JFLAP [closed]

Having this regular expression ((0 + 1)(11)* + 0)* I get this NFA according to me: I'm trying to compare it with the RE on JFlap and it says it's not equivalent ...
• 11
1 vote
57 views

### Need to create CFG that requires sum of other letters

I have a homework assignment that requires me to create CFG $G$ for $$L = \{a^i b^{i+j+k} c^j d^k\}$$ so that it can accept words like ab, aaabbbbd, abbbcd, but it should not accept abba, aabbbbbc, or ...
1k views

• 11
33 views

### prove that Every DPDA has an equivalent DPDA that always reads the entire input string

I am reading Michael Sipser's book Introduction to the Theory of Computation and in the section 2.4(chapter 2 and DCFLs section) there is a proof for the lemma that says "Every DPDA has an ...
1 vote
101 views

### What is the smallest NFA you can design for {a^n : n =/= 1003}

What is the smallest NFA that could be design for a^n where n!=1003? I have been racking my brain at this for a while but still can't reduce the number of states required from 1004. Here state(1003) ...
• 13
32 views

### Is there any way to tell which states are final states in a finite state automata given only its grammar?

Problem In the problem, I was given the grammar for a non-deterministic finite state automata (NDFSA). There was no other useful context given. The problem asks you to use this grammar to draw the ...
73 views

62 views

### Building the minimal automaton from the syntactic monoid of a language

I'm studying the algebraic view of automata theory. One of the basic results is that the syntactic monoid of a language $L$ is the transition monoid $M(A)$ of the minimal automaton $A(L)$ accepting $L$...
• 448
23 views

### Meaning of term $L(\bar{n})$

I was studying a few terms on finite automatas, and came across the following terms: $L(\bar{n})$ and $\overline{L(n)}$ The latter term stands for complement of a given NFA, but what does $L(\bar{n})$ ...
• 115
57 views

### Every DFA accepting a finite language must contain a dead state?

I came a across a question where there were some statements made on Finite Automata, DFA and their states. One such statements in the question was that a "Every DFA accepting a finite language ...
• 115
35 views

• 101
25 views

### find the minimization of the dfa

so this is the question , I have to minimize this DFA this is How I did it but when I checked for answers , this is what it was, can someone please explain to me what mistake I made? I have been ...
23 views

### In Pumpin Lemma, let's say we have a decomposition of the string s = xyz, is it necessary for x to take the automaton through distinct states?

I understand what Pumping Lemma is, how it works and also understand it's proof. The gist is that it uses "Pigeon Hole" principle to guarentee us a repeatation in the sequence of states and ...
40 views

• 15
106 views

### Confusion regarding the intuition behind epsilon transition in NFA

I am reading Michael Sipser's "Theory of Computation" 2nd edition, chapter 1 , Topic "Non determinism" ( Section 1.2 ) Let's use this E-NFA as an example My question is, do we ...
73 views

### When converting from nfa to dfa, do we always ignore the trap state?

Let's say we have a NFA such as follows: We know it's equivalent DFA is follows, after minimization: We know that when converting from NFA to DFA, the resultant DFA would have around 2^( number of ...