53
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 ...
16
This question is somewhat unclear to me; however, under one interpretation there is a result which indicates that the answer is unsatisfyingly yes: namely, the existence of Friedberg numberings. Roughly speaking, a Friedberg numbering is a programming language which is Turing complete but in which no two programs perform the same task.
(More formally: a ...
14
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 individual words. For instance, English has centre embeddings: you can build sentences of the form "the mouse escaped", "the mouse the cat chased escaped", "the ...
13
It doesn't really matter whether English (either words, or complete sentences) is a regular or say context free language or not. What matters is that it is very, very hard to produce a state engine or a grammar of a reasonable size whose language is reasonably close to the English language.
But let’s say we are told that English sentences are not allowed ...
9
The proof of Brzozowski's result is technical, but not very complicated.
In fact we only have to consider one sequence of reversal-determinization, to obtain the minimality result we want. (The first sequence of reversal determination leads to a deterministic FSA for the reversal of the original language; the minimality proof is for the second reversal-...
9
Here is a simple counter example:
$S \rightarrow aSbSaSbS \space |\space \epsilon$
and string $w: abababab.$
In one case we use last $S$ and in other case we use second $S$. All other $S$ goes to $\epsilon$.
Why I was able to get this grammar?
Let's rewrite above grammar with numbers assigned to each $S$'s.
$S \rightarrow aS_1bS_2aS_3bS_4 | \epsilon$
...
8
A popular reference is the article Undecidable Problems for Context-free Grammars by Hendrik Jan Hoogeboom.
The following is a proof taken from this note by Rob van Glabbeek.
Theorem: It is undecidable whether or not the languages generated by two given context-free grammars have an empty intersection.
Proof: By a reduction of post correspondence problem (...
8
(Making my comment into an answer as requested by Ben I.) English is so nebulous that it is not a regular language for the trivial reason that it is not even a well-defined language. It is just like asking why mathematics is not a regular language.
This may seem like a non-answer, and to some extent it is, because every question regarding English depends on ...
7
According to Parikh's theorem, if $L$ were context-free then the set $M = \{(a,b) : a \leq \gamma b \}$ would be semilinear, that is, it would be the union of finitely many sets of the form $S = u_0 + \mathbb{N} u_1 + \cdots + \mathbb{N} u_\ell$, for some $u_i = (a_i,b_i)$.
Obviously $u_0 \in M$, and moreover $u_i \in M$ for each $i > 0$, since otherwise ...
7
The complement of a context-free language $L$ is not necessarily context-free, but it is the difference between two context-free languages ($\Sigma^* - L$). (Here $\Sigma$ is the alphabet of $L$.)
See, for example, Is the complement of { ww | ... } context-free? for an example of a context-free language whose complement is not context-free.
7
The same "argument" would show that $\mathbb{N}$ is finite since it's the union of finite sets $$\mathbb{N}=\{0\}\cup\{0,1\}\cup\{0,1,2\}\cup ...$$ The point is that knowing that a given property is preserved under a given operation does not mean that it's preserved under "infinite iterations" of that operation.
6
The number of words of given length in a language is a very natural parameter. Here are some examples to pique your interest:
The density of $(1+01)^*$ is the Fibonacci sequence.
The density of a regular unary language is eventually periodic.
The density of a regular language is of the form $\Theta(n^k \lambda^n)$ for some integer $k \geq 0$ and real $\...
6
Every variable except $\gamma$ in this answer stands for a positive integer. It is well-known that given an irrational $\gamma>0$, there is a sequence of rational numbers $\dfrac{a_1}{b_1}\lt\dfrac{a_2}{b_2}\lt\dfrac{a_3}{b_3}\lt\cdots \lt\gamma$ such that $\dfrac{a_i}{b_i}$ is nearer to $\gamma$ than any other rational number smaller than $\gamma$ whose ...
6
No, just take as counter example $L_1=\epsilon$ and $L_2$ any other langage different from $L_1$.
6
Every $LL(k)$ grammar is $LR(k)$, but there are $LL(k)$ grammars which are not $LALR(k)$.
There's a simple example in Parsing Theory by Sippu&Soisalon-Soininen
$$\begin{align}S &\to a A a \mid b A b \mid a B b \mid b B a\\
A &\to c \\
B &\to c
\end{align}$$
The language of this grammar is finite, so it is obviously $LL(k)$. (In this case, $...
6
Contrary to what you wrote, context-free languages are not closed under complement. See Examples of context-free languages with a non-context-free complements for some examples. As a result, there is no such algorithm.
Also: It's decidable whether $L(S)=\emptyset$, but it's not decidable whether $L(S)=\Sigma^*$. If you could compute the complement, then ...
5
Your exam question makes very little sense. The obvious reading would be this:
Let $M$ and $N$ be two Turing machines. Why is it not possible to prove that $M$ and $N$ compute the same function?
More precisely:
It is not the case that for all Turing machines $M$ and $N$ it is provable that $M$ and $N$ compute the same function.
Well, this is quite ...
5
Using the terms as they are used in formal computer science, it is indeed true that any language with a finite longest word is regular. Here a language is a set of words over an alphabet, and a word over an alphabet is a sequence of symbols from the alphabet.
So if the language "English" is the set of words over a 26-symbol alphabet whose membership is ...
5
Unfortunately, your conjecture is wrong.
For instance $S \rightarrow aSSb | \epsilon$ is ambiguous.
To see that take $w: aabb$. For this string we have following two distinct derivation tree possible. In following derivation trees $e$ represents $\epsilon$
S S
/ / | \ / / | \
a S S b ...
5
The problem is likely hard, by reduction from SAT.
Let $\varphi$ be a CNF. For each clause $C$, we can construct a production which generates all truth assignments falsifying $C$. By going over all clauses, we can construct a grammar for all nonsatisfying truth assignments. For example, if the CNF is $(x_1 \lor x_2) \land (\lnot x_1 \lor x_3)$, the grammar ...
5
Your first proof is valid. You are assuming by contradiction that CFLs are closed under complement and arriving at the absurd conclusion that they must be closed under intersection. Notice that this works for any intersection operation between two CFL languages.
Your second proof is wrong. You would need to assume that CFLs are closed under union and arrive ...
5
There is no known natural example of such a pair, and indeed there are various results in computability theory suggesting that such a pair does not exist. So to whip up an example one has to do some work.
The simplest approach (indeed, the easiest I know) is via mutual diagonalization: we build inductively a pair of increasing sequences of infinite binary ...
5
Probably the most-used textbook today is:
Hopcroft, Motwani, & Ullman, Introduction to Automata Theory, Languages, and Computation (3rd edition).
A couple of other common ones are:
Sipser, Introduction to the Theory of Computation.
Linz, An Introduction to Formal Languages and Automata.
And a couple of older ones:
Michael Harrison, Introduction to ...
4
Note if $n<m$, we can write $a^nb^mc^qd^p$ as $a^nb^nb^xc^qd^{x+q}$ where $n,x,q$ are independent of each other. Otherwise, we can write $a^nb^mc^qd^p$ as $a^{m+y}b^mc^yc^pd^p$ where $m,y,p$ are independent of each other.
So the grammar can be $S\rightarrow S_1S_2\mid S_3S_4$, where $S_1$ generates $a^nb^n$, $S_2$ generates $b^xc^qd^{x+q}$, $S_3$ ...
4
$E_L(n)$ describes how many bits of information you get from a string of length $n$, assuming it belongs to the language.
For many languages the function would be a rather smooth function in $n$. There are of course languages where the language only contains strings of even length, for example, in which case $E_L(n)$ isn't even defined for odd $n$.
$E_L(...
4
Density is what you get when you want a measure for the size of infinite languages. We can't quantify that by just taking their number of elements, which is the same for all infinite languages: (enumerable) infinity.
Still, we have an intuition about the relative sizes of infinite languages. For instance, about the language of all even strings over a given ...
4
No, there isn't. It is undecidable, even for context-free languages. It is decidable for deterministic context-free languages.
References are easy to find with Google; for instance,
Undecidable Problems for Context-free Grammars, by Hendrik Jan Hoogeboom
Deciding whether a context-free language is regular [closed], on the Theoretical Computer Science Stack ...
4
The class of regular languages is closured under various closure operations, such as union, intersection, complement, homomorphism, regular substitution, inverse homomorphism, and more. This can be used to prove that a given language is not regular by reduction to a language which is already known to be non-regular.
As a very simple example, suppose that we ...
4
Let us check the definition.
For two sets of strings $S_1$ and $S_2$, the concatenation $S_1\cdot S_2$ consists of all strings of the form $vw$ where $v$ is a string from $S_1$ and $w$ is a string from $S_2$, or formally $S_1\cdot S_2 = \{ vw : v \in S_1, w \in S_2 \}$.
What about $\emptyset\cdot R$?
Since there is no string in the empty set, we cannot ...
4
You're probably confusing $\emptyset$, the langauge that contains no strings at all, with $\{\varepsilon\}$, the language that contains only the empty string.
Only top voted, non community-wiki answers of a minimum length are eligible
