54

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, there is no DFA deciding whether it is a well-written paragraph in the English language. Of course, it can say whether each word is an English word or not, but ...


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 ...


38

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 ...


30

So given a regular language $L$, we know (essentially by definition) that it is accepted by some finite automaton, 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. ...


30

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)$. ...


28

You have to show that you can always construct a finite automaton that accepts strings in $L^R$ given a finite automaton that accepts strings in $L$. Here is a procedure to do that. Reverse all the links in the automaton Add a new state (call it $q_s$) Draw a link labeled with $\epsilon$ from state $q_s$ to every final state Turn all the final states into ...


28

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$. ...


28

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.


27

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 ...


26

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.


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, ...


23

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 ...


22

Grammars are inherently recursive objects, so the answer seems obvious: by induction. That said, the specifics are often tricky to get right. In the sequel I will describe a technique that allows to reduce many a grammar-correctness proof to mechanical steps, provided some creative preprocessing is done. $\newcommand{\lang}[1]{\mathcal{L}(#1)} \newcommand{\...


22

$0^*$ is the set of finite strings consisting only of $0$. There are no possibly infinite strings in $0^*$. It is trivially regular because the regex $0^*$ accepts exactly $A$ by definition. All regular problems are computable so we can definitely create a Turing machine for it (look up NFA's and DFA's for more info on the connection of Turing machines to ...


22

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-terminal symbol. Sometimes people abbreviate "production rules" to "productions". Sometimes people abbreviate "production rules" to "rules". The two are not ...


21

I'm a bit confused by your question: you're asking if the Turing machine is recognizable, but I think you mean to ask if the language $\{1^x \mid x \in \mathbb{N}\}$ is recognizable. A language is recognizable if and only if we can build a Turing machine that accepts every string in the language, and does not accept any string not in the language. And we ...


20

A grammar (not a language!) is ambiguous if there is a word with two "essentially different" parses. Roman numerals are unambiguous - given a roman numeral, it has an unambiguous numerical value. The fact that this correspondence is not one-to-one is beside the point.


20

The powerset of the language contains all the sublanguages. This will be uncountably infinite, but there are only countably many regular languages (for a particular, finite alphabet)


20

You are misunderstanding how accepting a language works. A language $L$ is in P iff there is a deterministic Turing Machine that decides whether a word $w$ belongs to $L$ in polynomial time. Deciding means that it return a positive answer iff $w \in L$ and a negative otherwise. Your approach will return a positive answer in every case. Thus your TM will ...


20

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 incomplete. But they don't satisfy all of the requirements of algorithms which require complete DFAs, and the complement algorithm you are using is one of those. (...


19

To add to the automata-based transformations described above, you can also prove that regular languages are closed under reversal by showing how to convert a regular expression for $L$ into a regular expression for $L^R$. To do so, we'll define a function $REV$ on regular expressions that accepts as input a regular expression $R$ for some language $L$, then ...


19

With only union and concatenation, you can't describe any infinite language. The union and concatenation can only produce finitely many strings. With only union and the Kleene star, you can't describe a language such as $L = \{ab\}$, because there's no way to concatenate an expression generating only $a$ with an expression generating only $b$. With only ...


19

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 many textbooks) states that the language of a regular expression is regular. Since $a^* b^*$ is a regular expression, its language must be regular (if you believe ...


18

Gödel numbering in computer science means more or less "source code" and "data in binary format", so I hope the significance of this should be obvious if I can convince you that this really is so. Before modern computers came into existence, people made single-purpose computing devices (I am telling you a story, not a history), for example someone made a ...


18

A problem is recursive or decidable if a machine can compute the answer. A problem is recursively enumerable or semidecidable if a machine can be convinced that the answer is positive.


18

Yes. You don't need the excluded middle to derive a contradiction. In particular, diagonalisation still works. Here is a typical diagonalisation argument by Conor McBride. This particular diagonalisation is about incompleteness, not undecidability, but the idea is the same. The important point to notice is that the contradiction he derives is not of the ...


18

@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.


17

One can understand your question in two ways, according to the definition of "the complement of CFL". case A: Complement of CFL is the class of all the languages that are not in CFL. Formally, $$\overline{CFL} = \{ L \mid L\notin CFL\}.$$ In that case, $\overline{CFL}$ is way bigger than $P$, it even has languages that are not in $R$, etc. But maybe that's ...


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