# Tag Info

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


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