55 votes

Why is English not a regular language?

The English language is regular if you consider it as a set of single words. However, English is more than a set of words in a dictionary. English grammar is the non-regular part. Given a paragraph, ...
Narek Bojikian's user avatar
39 votes

Can a language have more than one DFA?

First of all, your left DFA is incorrect - it accepts e.g. 011. Secondly, DFAs can be canonically minimized, so in that sense, you can always find one canonical DFA for a certain language. But in ...
Shaull's user avatar
  • 17.1k
36 votes
Accepted

Planar regular languages

It isn't true that every DFA for this language is non-planar: Here is a language that is truly non-planar: $$ \left\{ x \in \{\sigma_1,\ldots,\sigma_6\}^* \middle| \sum_{i=1}^6 i\#_{\sigma_i}(x) \...
Yuval Filmus's user avatar
35 votes

Are there any non-finite automata?

The full name is "finite state automata". The crucial part is that the state of the automaton can be fully characterized by an element of some finite set of discrete states. This means that if the (...
alexis's user avatar
  • 453
34 votes
Accepted

Are there any non-finite automata?

All automaton models you'll typically encounter are finitely represented; otherwise there would be uncountably many, which means they are not captured by Turing-complete models. Or, in CS-think, they'...
Raphael's user avatar
  • 72.3k
31 votes
Accepted

Proving Equivalence of Two Regular Expressions

One way to prove that two regular expressions $r_1,r_2$ generate the same language is to show both inclusions: Show that if $w$ is generated by $r_1$ then it is generated by $r_2$. Show that if $w$ ...
Yuval Filmus's user avatar
28 votes

Planar regular languages

The concept has been researched before. (Once you know the answer, google for it ...) First there is old work by Book and Chandra, with the following abstract. Summary. It is shown that for every ...
Hendrik Jan's user avatar
  • 30.4k
28 votes

Can a deterministic finite automaton ever go into an infinite loop?

A deterministic finite automaton can only go to infinite loop if the input string is infinite. For finite inputs, the automaton stops when the input string ends. For infinite inputs, for example the ...
Laakeri's user avatar
  • 1,339
24 votes

Is it mandatory to define transitions on every possible alphabet in Deterministic Finite Automata?

Suppose a DFA was allowed to have missing transitions. What happens if you encounter a symbol which has no transtion defined for it? The result is undefined. That would seem to violate the "...
Nathan Davis's user avatar
23 votes

How did the word "production" end up being a synonym with the word "rule" in the context of Computer Science?

A grammar has "Production rules:" rules about the new sequences of symbols that you can produce from old sequences. In the cases of context-free grammars, this the old sequence is always a single non-...
Joey Eremondi's user avatar
23 votes
Accepted

Why NFA is called Non-deterministic?

"Deterministic" means "if you put the system in the same situation twice, it is guaranteed to make the same choice both times". "Non-deterministic" means "not deterministic", or in other words, "if ...
D.W.'s user avatar
  • 158k
23 votes
Accepted

Is the equality of two DFAs a decidable problem?

In order to decide whether the languages generated by two DFAs $A_1,A_2$ by the same, construct a DFA $A_\Delta$ for the symmetric difference $L(A_1) \Delta L(A_2) := (L(A_1) \setminus L(A_2)) \cup (L(...
Yuval Filmus's user avatar
22 votes
Accepted

Why are Linearly Bounded Turing Machines more powerful than Finite State Automata?

The linear bounded Turing machine is restricted to a tape whose length is a linear function of the length of the input. If the length limit were a constant, then the machine would be no more powerful ...
rici's user avatar
  • 12k
22 votes
Accepted

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

There is no unique way of converting a regex into NFA. That is, for any regular language $L$ there exist multiple (even, infinite) number of NFAs that accept the language $L$. The solution of your ...
Ran G.'s user avatar
  • 20.7k
19 votes

Are there any non-finite automata?

In a finite automaton, there is quite a bit of finiteness: the number of states, the size of the underlying alphabet, and the lengths of the strings accepted by the machine. You can certainly relax ...
Rick Decker's user avatar
  • 14.8k
19 votes

Are Finite Automata Turing Complete?

No finite automaton can simulate a Universal Turing machine, so finite automatons are not Turing complete. This falls out immediately from them having a finite number of states. Universal Turing ...
Curtis F's user avatar
  • 1,043
19 votes

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

Not a complete proof, but a picture that hints to a solution. If you start at a random point and add the numbers, then after a complete circle you end again at the initial zero. Track all the ...
Hendrik Jan's user avatar
  • 30.4k
18 votes

How to prove using pumping lemma that language generated by a(b*)c(d*)e is regular?

You can't. The pumping lemma can only be used to prove that a language is non-regular. How to prove that it is regular depends on how you've defined regular languages. You (or your course or textbook) ...
David Richerby's user avatar
17 votes
Accepted

Finite state automata: final states

You seem to have a misunderstanding of generative models v.s. "recognizing" models. The grammar you have on the right generates words by applying rules, starting from the initial variable, and ...
Shaull's user avatar
  • 17.1k
16 votes
Accepted

Any problem solved by a finite automaton is in P

Yes, it is true. In terms of complexity classes, $$ \text{REG} \subseteq \text{P}, $$ where $\text{REG}$ is the class of regular languages (i.e., problems that can be solved by a finite automaton). ...
Caleb Stanford's user avatar
16 votes
Accepted

How to prove using pumping lemma that language generated by a(b*)c(d*)e is regular?

The pumping lemma states a proprety of regular languages: If $L$ is a regular language then there exists an integer $p$ such that if $w \in L$ has length at least $p$ then it can be written as $w = ...
Yuval Filmus's user avatar
16 votes

Why is English not a regular language?

Expansion of my comments to narek Bojikian's answer: When people talk about natural languages such as English not being regular, they're usually talking on the level of grammar (syntax) rather than ...
rlms's user avatar
  • 510
16 votes
Accepted

Prove that every substring closed language L ⊆ {0, 1}* is regular

There are some substring-closed languages that are not regular. Here is an example. Let $C=\{01^n0^n1\mid n\ge1\}$ and $F=\{f\mid \exists c\in C, f\preceq c\}$, i.e., $F$ is the language of all ...
John L.'s user avatar
  • 38.8k
15 votes
Accepted

How to determine if an automata (DFA) accepts an infinite or finite language?

This is well enough known that you should be able to find it in most intro theory texts: Theorem. The language accepted by a DFA $M$ with $n$ states is infinite if and only if $M$ accepts a string of ...
Rick Decker's user avatar
  • 14.8k
15 votes
Accepted

Can we transfer every DFA to DFAs with start state having no in edge?

It is possible. You just need to duplicate the start state, one copy becoming the starting state with no in-edge, the other copy becoming a state that can have in-edges. Formally, if $A = (Q, \delta, ...
Nathaniel's user avatar
  • 13.9k
14 votes

Why is every finite language A ⊆ Σ* regular

The proof goes something like this: If $A$ is a finite language, then it contains a finite number of strings $a_0, a_1, \cdots , a_n$. The language $\{a_i\}$ consisting of a single literal string $...
Draconis's user avatar
  • 7,078
14 votes
Accepted

Can a DFA have an unreachable state?

You are indeed allowed to have unreachable states in DFAs (or NFAs, or various other automata models). You may wonder what is the point of having them, given that they are unreachable and have no ...
Shaull's user avatar
  • 17.1k
14 votes
Accepted

Why does a DFA have multiple final states?

A DFA is a machine that reads in its input left to right, and, while reading, keeps track of its internal state. At the end, it has to decide whether to "accept" or "reject" the input based only on ...
Caleb Stanford's user avatar
13 votes
Accepted

Why should we study all the three forms of representation of finite automata?

Add regular grammars for a fourth. There are others... Part of the interest in DFA + NFA is that they are simple computation models, with NFA (and $\epsilon$-NFA) examples of nondeterminism (a ...
vonbrand's user avatar
  • 14k
13 votes
Accepted

Is it possible to build DFA for odd-length words with 1 in the middle?

No, you can not. Proof by Pumping Lemma: Assume $L$ is regular and $n$ be the pumping length consider the word $w=0^n10^n$. Thus there are $x,y,z \in \{0,1\}^*$ with $|xy|<n$ and $|y| > 0$ such $...
Martin Glauer's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible