Skip to main content
56 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
40 votes
Accepted

Why is there no permutation in Regexes? (Even if regular languages seem to be able to do this)

The fundamental theorems of formal language theory are that regular expressions, regular grammars, deterministic finite automata (DFAs) and nondeterministic finite automata (NFAs) all describe the ...
David Richerby's user avatar
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
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.7k
26 votes

Is there any uncountable Turing decidable language?

Every language over a finite (or even countable) alphabet is countable. Assuming your Turing machine alphabet is finite, any language it can possibly accept is countable.
Yuval Filmus's user avatar
25 votes
Accepted

Is it possible to build any regular expression in a computer language with just 3 basic operators?

Regular expressions using only concatenation, alternation and Kleene star describe regular languages. In contrast, extended regular expressions available in modern programming languages can describe ...
Yuval Filmus's user avatar
24 votes
Accepted

Regular languages that seem irregular

My favorite example of this, which is often used as a difficult/tricky exercise, is the language: $$L=\{w\in \{0,1\}^*:w \text{ has an equal number of } 01\text{ and }10\}$$ This has the strong flavor ...
Shaull's user avatar
  • 17.2k
21 votes
Accepted

Complement of a DFA without final states

It's common to write DFAs which don't have transitions on every symbol. These are called "incomplete" DFAs, and there is really nothing wrong with them as long as it is understood that they are ...
rici's user avatar
  • 12k
20 votes
Accepted

Will $L = \{a^* b^*\}$ be classified as a regular language?

A language is regular, by definition, if it is accepted by some DFA. (This is at least one common definition.) Can you think of a DFA accepting the language? A well-known result (that is proved in ...
Yuval Filmus's user avatar
19 votes
Accepted

Is Python a context-free language?

Context-free grammars cannot express the rules of INDENT/DEDENT and so Python (which we use today in practice with INDENTs/DEDENTs)is not pure CF. Parsers (or lexical analyzers or lexers) for these ...
fade2black's user avatar
  • 9,837
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
18 votes

If L is not regular and is a proper subset of L1, does it follow that L1 is not regular?

@Vladislav's answer is probably more interesting, but observe that every language over an alphabet $\Sigma$ is a subset of $\Sigma^*$, which is certainly a regular language.
rici's user avatar
  • 12k
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.2k
17 votes

Why is there no permutation in Regexes? (Even if regular languages seem to be able to do this)

So my question is: (Why) Is my proof wrong? If it is right: Why is there no easy way to express permutations? Your "proof" only looked at permutations of single words, which are finite ...
Paŭlo Ebermann's user avatar
17 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
  • 520
17 votes

Is $\{w_1xw_2\mid w_1,w_2\in \{a,b\}^* \text{ and } x \in \{a,b\}\}$ regular or not?

The language is regular and a possible regular expression for $L$ is $(a\mid b)^* (a \mid b) (a \mid b)^* = (a \mid b)^+$.
Steven's user avatar
  • 29.5k
17 votes
Accepted

Is $\{w_1xw_2\mid w_1,w_2\in \{a,b\}^* \text{ and } x \in \{a,b\}\}$ regular or not?

It's regular because your language is equal to (suppose $\Sigma=\{a,b\}$) $$L=\Sigma^*\Sigma\Sigma^*$$ $$=\Sigma^+.$$ So we can represent $L$ by regular expression: $$(a+b)^*(a+b)(a+b)^*$$ $$=(a+b)^+.$...
ErroR's user avatar
  • 1,920
16 votes
Accepted

Is there any uncountable Turing decidable language?

We can have uncountable languages only if we allow words of infinite length, see for example Omega-regular language. These languages are called $\omega$-languages. Another example will be language of ...
Sarvottamananda's user avatar
16 votes
Accepted

Why are regular expressions defined with union, concatenation and star operations?

1) If we also allow intersection and complement, then the resulting expressions are sometimes called extended regular expressions; as the regular languages are closed under boolean operations nothing ...
StefanH's user avatar
  • 1,439
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
Accepted

Prove that A** = A*, where A is a language over Σ*

Since $L \subseteq L^*$ for all $L$, we have $\mathcal{A}^* \subseteq \mathcal{A}^{**}$. In the other direction, suppose that $w \in \mathcal{A}^{**}$. Then there exists an integer $n \geq 0$ and ...
Yuval Filmus's user avatar
15 votes
Accepted

Is there an analog of "regular" for infinite strings?

Probably the most specific term to describe your first string, $010101\dots$ is periodic. A string $x_1x_2\dots$ (finite or infinite) is periodic if there is some $t$ such that, for all $i$, ...
David Richerby's user avatar
15 votes
Accepted

How to determine minimum word length of regular language

First, notice that you can easily eliminate $\emptyset$ for all regular expressions other than a regular expression describing the empty language. To do this, you use the following rewriting rules, ...
Yuval Filmus's user avatar
15 votes
Accepted

Prove or Disprove: an infinite intersection of regular languages is a context-free language

"I know that this statement is false, but couldn't find an example to disprove it." It might come as a surprise to you that, in fact, every non-context-free language can be a counterexample. ...
John L.'s user avatar
  • 39k
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
  • 15.7k
14 votes

Will $L = \{a^* b^*\}$ be classified as a regular language?

$\{a^* b^*\}$ is a regular language, since it's generated by a regular expression. The key difference between $L_* = \{a^* b^*\}$ and $L_= = \{a^n b^n\}$ is that $L_=$ requires counting the $a$'s and ...
Gilles 'SO- stop being evil''s user avatar
14 votes

Proving the regularity of a certain language

It is a trick question. You can find a simpler form to describe the language.
Hendrik Jan's user avatar
  • 30.7k
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,138
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.2k

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