92

There are several methods to do the conversion from finite automata to regular expressions. Here I will describe the one usually taught in school which is very visual. I believe it is the most used in practice. However, writing the algorithm is not such a good idea. State removal method This algorithm is about handling the graph of the automaton and is ...


69

To my knowledge the pumping lemma is by far the simplest and most-used technique. If you find it hard, try the regular version first, it's not that bad. There are some other means for languages that are far from context free. For example undecidable languages are trivially not context free. That said, I am also interested in other techniques than the ...


59

There are numerous containments known. Let $\subseteq$ denote containment and $\subset$ proper containment. Let $\times$ denote incomparability. Let $LL = \bigcup_k LL(k)$, $LR = \bigcup_k LR(k)$. Grammar level For LL $LL(0) \subset LL(1) \subset LL(2) \subset LL(2) \subset \cdots \subset LL(k) \subset \cdots \subset LL \subset LL(*)$ $SLL(1) = LL(1), ...


58

Proof by contradiction is often used to show that a language is not regular: let $P$ a property true for all regular languages, if your specific language does not verify $P$, then it's not regular. The following properties can be used: The pumping lemma, as exemplified in Dave's answer; Closure properties of regular languages (set operations, concatenation, ...


53

For simplicity, I'll begin by only considering "decision" problems, which have a yes/no answer. Function problems work roughly the same way, except instead of yes/no, there is a specific output word associated with each input word. Language: a language is simply a set of strings. If you have an alphabet, such as $\Sigma$, then $\Sigma^*$ is the set of all ...


49

Method The nicest method I have seen is one that expresses the automaton as equation system of (regular) languages which can be solved. It is in particular nice as it seems to yield more concise expressions than other methods. Let $A= (Q,\Sigma,\delta,q_0,F)$ an NFA without $\varepsilon$-transitions. For every state $q_i$, create the equation $\qquad \...


47

Yes, if you can come up with any of the following: deterministic finite automaton (DFA), nondeterministic finite automaton (NFA), regular expression (regexp of formal languages) or regular grammar for some language $L$, then $L$ is regular. There are more equivalent models, but the above are the most common. There are also useful properties outside of the ...


45

Ogden's Lemma Lemma (Ogden). Let $L$ be a context-free language. Then there is a constant $N$ such that for every $z\in L$ and any way of marking $N$ or more positions (symbols) of $z$ as "distinguished positions", then $z$ can be written as $z=uvwxy$, such that $vx$ has at least one distinguished position. $vwx$ has at most $N$ distinguished ...


36

Based on Dave's answer, here is a step-by-step "manual" for using the pumping lemma. Recall the pumping lemma (taken from Dave's answer, taken form Wikipedia): Let $L$ be a regular language. Then there exists an integer $n\ge 1$ (depending only on $L$) such that every string $w$ in $L$ of length at least $n$ ($n$ is called the "pumping length") can be ...


35

Claim: $L$ is context-free. Proof Idea: There has to be at least one difference between the first and second half; we give a grammar that makes sure to generate one and leaves the rest arbitrary. Proof: For sake of simplicity, assume a binary alphabet $\Sigma = \{a,b\}$. The proof readily extends to other sizes. Consider the grammar $G$: $\qquad\begin{...


34

Closure Properties Once you have a small collection of non-context-free languages you can often use closure properties of $\mathrm{CFL}$ like this: Assume $L \in \mathrm{CFL}$. Then, by closure property X (together with Y), $L' \in \mathrm{CFL}$. This contradicts $L' \notin \mathrm{CFL}$ which we know to hold, therefore $L \notin \mathrm{CFL}$. This is ...


34

Your conjecture is disproved by Keith Ellul, Bryan Krawetz, Jeffrey Shallit and Ming-wei Wang in their paper "Regular Expressions: New Results and Open Problems". While the paper is not available on-line, a talk is. In the paper, they define the measure $|\mathrm{alph}(R)|$, which is the number of symbols in $R$, not counting $\epsilon$ or $\emptyset$. ...


34

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 same kinds of languages: namely the regular languages. The fact that we can describe these languages in so many completely different ways suggests that there's ...


32

Before I can tell you why there are arbitrarily long sentences in English, I would like to point out that 1 is a number, 2 is a number, 3 is a number, 4 is a number, 5 is a number, 6 is a number, 7 is a number, 8 is a number, 9 is a number, 10 is a number, 11 is a number, 12 is a number, 13 is a number, 14 is a number, 15 is a number, 16 is a number, 17 is a ...


29

If a language $L$ is deterministic, it is accepted by some deterministic push-down automaton, which in turn means there is some LR(1) grammar describing the language, and as every LR(1) grammar is unambiguous, this means that $L$ cannot be inherently ambiguous. Knuth proved this in his paper in which he introduced LR(1) (On the Translation of Languages from ...


28

From Wikipedia, the pumping language for regular languages is the following: Let $L$ be a regular language. Then there exists an integer $p\ge 1$ (depending only on $L$) such that every string $w$ in $L$ of length at least $p$ ($p$ is called the "pumping length") can be written as $w = xyz$ (i.e., $w$ can be divided into three substrings), satisfying ...


28

As Kaveh says in a comment, Kleene bestowed the name way back when he kicked off automata theory and formal languages. I believe the term was arbitrary, though it has been many years since I read his original paper. Mathematicians have a habit of hijacking common nouns and adjectives for mathematical objects and properties, sometimes with good reasons such ...


28

You are right - we cannot allow "pumping" words of a finite $L$. The thing you are missing is that the lemma says there exists a number $p$, but does not tell us the number. All words longer than $p$ can be pumped, by the lemma. For a finite $L$, it happens so that $p$ is larger than the length of the longest word in $L$. Thus, the lemma only holds ...


27

Brzozowski algebraic method This is the same method as the one described in Raphael's answer, but from a point of view of a systematic algorithm, and then, indeed, the algorithm. It turns out to be easy and natural to implement once you know where to begin. Also it may be easier by hand if drawing all the automata is impractical for some reason. When ...


27

It's context-free. Here's the grammar: $S \to A | B|AB|BA$ $A \to a|aAa|aAb|bAb|bAa$ $B \to b|aBa|aBb|bBb|bBa$ $A$ generates words of odd length with $a$ in the center. Same for $B$ and $b$. I'll present a proof that this grammar is correct. Let $L = \{a,b\}^* \setminus \{ww \mid w \in \{a,b\}^*\}$ (the language in the question). Theorem. $L = L(S)$. ...


26

So given a regular language $L$, we know (essentially by definition) that it is accepted by some finite automata, so there's a finite set of states with appropriate transitions that take us from the starting state to the accepting state if and only if the input is a string in $L$. We can even insist that there's only one accepting state, to simplify things. ...


26

There's a significant difference between the question as you pose it and the question posed in the exercise. The question asks for an example of a set of regular languages $L_{1}, L_{2}, \ldots$ such that their union $$ L = \bigcup_{i=1}^{\infty}L_{i} $$ is not regular. Note the range of the union: $1$ to $\infty$. Regular languages are closed under finite ...


25

Oh my. This seems like a confusion caused by the (old school) terminology of "finite-state language" as a synonym for what is known today as "regular language". Anyways, the standard definitions for finite/infinite accepted these days regard only the size of the language: a finite language is any set $L$ of strings, of finite cardinality, $|L|<\infty$. ...


24

You can recognize the canonical non-context-free (but context-sensitive) language $\{ a^n b^n c^n\ |\ n \geq 1 \}$ with this type of state machine. The crux is that you add tokens to the heap for every $a$ character, and while parsing the $b$ characters, you add 'larger' tokens to the heap, so they only end up at the bottom of the heap when you have parsed ...


24

The algorithm you refer to is called the Powerset Construction, and was first published by Michael Rabin and Dana Scott in 1959. To answer your question as stated in the title, there is no maximal DFA for a regular language, since you can always take a DFA and add as many states as you want with transitions between them, but with no transitions between one ...


24

Since you wanted "strings", I mention the classic one: Post Correspondence Problem.


24

Transitive closure method This method is easy to write in a form of an algorithm, but generates absurdly large regular expressions and is impractical if you do it by hand, mostly because this is too systematic. It is a good and simple solution for an algorithm though. The key idea Let $R^k_{i,j}$ represent the regular expression for the strings going from ...


24

Consider Lagrange's four square theorem. It states that if $B = \{1^{n^2}| n \geq 0\}$ then $B^4 = \{1^n | n \geq 0\}$. If $B^2$ is regular, take $A = B$ else take $A = B^2$. Either way, this proves the existence of irregular $A$ such that $A^2$ is regular.


24

Whoever told you that regular expressions are used to parse code was spreading disinformation. Classically (I don't know to what extent this is true in modern compilers), the parsing of code – conversion of code from text to a syntax tree – is composed of two stages: Lexical analysis: Processes the raw text into chunks such as keywords, numerical constants, ...


24

If regular expressions were allowed to be infinite, then any language would have been regular. Given the language $L=\{w_1, w_2, \ldots\}$, we can always define the regular expression $R = w_1 + w_2 + \cdots$, which exactly defines $L$. (Example: the regular expression $R_1 = \epsilon+0+1+00+01+10+11+\cdots$ defines $L_1=\{0,1\}^*$.) We know that some ...


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