New answers tagged formal-languages
1
First, we know that, $L$ is a regular language if and only if its complement be regular language.
On the other hand, $$L_1\setminus L_2=L_1\cap L_2^c.$$
Suppose $\Sigma=\{a,b\}$, Let $L_1=\Sigma^*$ , and $L_2=\Sigma^*\setminus \{a^nb^n\}$, obviously, $L_2$ isn't regular, so
$$L_1\setminus L_2=\{a^nb^n\} $$
consequently, $L_1\setminus L_2$ can be a non-...
14
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)^+.$$
17
The language is regular and a possible regular expression for $L$ is $(a\mid b)^* (a \mid b) (a \mid b)^* = (a \mid b)^+$.
2
The grammatical classification of the sentence types you're asking about isn't well-defined for programming languages because they refer to common ways humans respond to being talked to, which don't apply closely to computers.
The declarative, interrogative, imperative and exclamative grammatical forms are so named because those are the purposes to which ...
1
I see the misconception. We have a name collision, where the same word is used to mean two different things in two different contexts.
When Wikipedia says that SQL is a declarative programming language, that has little or nothing to do with the notion of a declarative sentence in English / natural language. Despite both appearing to use the same word "...
0
Rice's theorem states that if $L_S$ is not trivial (i.e., is not $\varnothing$ nor all languages) then $L_S$ can't be decided (it might be computationally enumerable, though).
An extension to Rice's theorem states that $L_S$ is computationally enumerable if and only if:
For all $L_1, L_2$ computationally enumerable, if $L_1 \in L_S$ and $L_1 \subset L_2$, ...
-1
Take a look at Rice's theorem and its extensions.
Basically, Rice's theorem and its extension state:
If $\emptyset\neq S\subset RE$ then $L_S\notin R$
If $\emptyset \neq S\subset RE$ and $\Sigma^*\notin S$ (please fix me if this is wrong, this is what I remember) then $L_S\notin RE$
2
Look at the Swift language where the available operators are not defined in the language, but in the standard library. There are rules that let the compiler distinguish between binary and unary operators. An expression is operands, possibly preceded or followed by unary operators, and separated by binary operators.
That’s decided by the grammar, without any ...
2
First note that the statement is somewhat artificially made complex, probably to muddle the solution.
The languages considered are $L_1^C \cup L_2$ and
$L_2 \setminus L_1 = L_2 \cap L_1^C$.
Now replace $L_1$ by its complement, and we obtain
$L_1 \cup L_2$ and
$L_1 \cap L_2$.
In order to find a counter example it suffices to find a regular $L_1$ and a ...
2
Let $\Sigma=\{0,1\}$ and denote by $|w|_1$ the number of occurrences of $1$ in $w \in \Sigma^*$.
Pick $L_1 = \{w \in \Sigma^* \mid |w|_1 \equiv 1 \pmod 2\}$ and $L_2 = \{0^n1^n \mid n \ge 0\}$.
Suppose that $L' = L_1^C \cup L_2$ was regular.
Then a necessary condition for $L'$ to be regular is for $L^{(1)} = L' \setminus L_1^C = L_2 \setminus L_1^C = \{ 0^{...
0
A unary language (a language over a unary alphabet) is context-free iff it is regular. Moreover, such a language is context-free (or regular) iff the set of lengths of words in the language is eventually periodic.
The set $\{n^2 : n \in \mathbb{N}\}$ is not eventually periodic: the gap between adjacent elements increases without bound. So the language $\{a^{...
0
If still have your question, I thought this might help why using pump up i=2 we can show the language is not Context Free.
Let $s=a^{p^2}$
next string is for (n+1) : $s=a^{(p+1)^2}$
$s=uvxyz$$; |vxy|\leq P$$;|vy|\geq1$
at most length $|vy|=p$
pump up i=2 so the pumped string $p^2+p$ which is not in the language because:
$ (p+1)^2 $>$ (p^2+p)$
so the ...
3
From the supplied solution, it's clear that the question was written incorrectly. The fifth, sixth and seventh productions should produce $X$, $Y$ and $Z$, respectively, instead of $A$, $B$ and $C$. You might want to report this typo to whomever set the problem.
Once you make that change, the fact that it is equivalent to a right-linear grammar can be shown ...
1
If you look at the formal definition of grammars, there is nothing requiring a nonterminal symbol to apppear in the left side of a production rule.
So $G$ is a perfectly valid grammar.
If we drop all useless production we are left with $S \to \lambda$. Therefore $L(G) = \{ \lambda\}$, which is a finite language and hence it is also regular. If you really ...
1
For (1) you can take the length of the input. There are many algorithms to compute digits of $\pi$. Use any of them to compute the same number of digits as the input and compare.
For (2) we observe that when some $n\in A_2$, then all $k<n$ also are in $A_2$. Therefore, either all $n\in A_2$ or there is a maximum $n=n_0$ that belongs to $A_2$. Therefore, ...
1
If $n \neq 2m$ then either $n < 2m$ or $n > 2m$.
A grammar for the former case is:
$$
S_1 \to XY \mid aXY \mid Y \mid aY\\
X \to aaXb \mid aab \\
Y \to bY \mid b;
$$
where $X$ generates all words of the form $a^{2k} b^k$ for some positive $k$.
A grammar for the latter case is:
$$
S_2 \to ZX \mid Z\\
X \to aaXb \mid aab \\
Z \to aZ \mid a;
$$
A ...
2
$L(G)$ is regular and hence not inherently ambiguous.
In particular $L(G)$ is the language described by the regular expression $a(xa)^*$.
0
I think this is the solution:
$$S\to \epsilon \mid aaSbb $$
Top 50 recent answers are included
