57
Practically no programming language, modern or ancient, is truly context-free, regardless of what people will tell you. But it hardly matters. Every programming language can be parsed; otherwise, it wouldn't be very useful. So all the deviations from context freeness have been dealt with.
What people usually mean when they tell you that programming languages ...
7
There is an example, and $L = \{a^nb^na^{2m}b^ka^k \mid n,m,k \in \mathbb{N}\}$ does the trick. We get that $\sqrt{L} = \{a^nb^na^n \mid n \in \mathbb{N}\}$, which is a standard example of a non-context-free language.
To elaborate a bit on how to get there: CFLs can express that two numbers are the same, but not that three numbers are the same. So I want the ...
3
Every language is a union of infinitely many regular languages:
$$
L = \bigcup_{w \in L} \{w\}.
$$
3
It is regular since $a^*(bb)^* \setminus L$ is regular:
$a^*(bb)^*\setminus L = a^* \cup (bb)^* \cup \{a^mb^{2n}|1\leq mn < 3\}$
The last language of the union is finite thus regular.
3
Nondeterministic guess is a non formal term we use for two (or more) possible transitions from the same configuration. When talking about a non deterministic finite automata, if a state $q$ has two different transitions for the character $a$, and I want to show that it accepts a certain word $w$, then I treat the junction at $q$ where $a$ is read as the ...
3
You can write this language as the intersection of two languages:
$$
\{ x \# y \mid xy \in L \} \cap \{ y \# x \mid xy \notin L \}
$$
I assume you know how to handle the first one. As for the second one, construct an NFA that acts as follows:
Start with a DFA for $L$.
Guess which state the DFA will be on after reading $x$.
Based on this guess, verify that ...
2
I would approach this question in this way, (k) in $\mathrm{LL}(k)$ means the number of lookaheads. The grammar of $\mathrm{L}$ here possess non-determinism. For example, if you can only see aaaa then by just looking at the first k symbols, you can't make the decision whether it is aaaa or aaaabbbb.
No matter how large the value of k is, there will always be ...
2
Rosenkrantz and Stearns prove in their paper Properties of deterministic top-down grammars that the language
$$ \{ a^n b^n : n \ge 0 \} \cup \{ a^n c^n : n \ge 0 \} $$
is not $\mathrm{LL}(k)$ for any $k$ (see page 246). Presumably a similar proof will show that your language is not $\mathrm{LL}(k)$ for any $k$.
You mention a confusion between grammars and ...
2
Your language is regular. Indeed, the condition $nm \geq 3$ is equivalent to ($n = 1$ and $m \geq 3$) or ($n \geq 3$ and $m = 1$) or ($n \geq 2$ and $m \geq 2$). It is described by the regular expression $$ a (bb)^3(bb)^* + a^3a^*bb + a^2a^*(bb)^2(bb)^*. $$
2
Assume towards contradiction that the language is regular.
Let a be the "pumping length" given by the pumping lemma.
Let $p \geq a+2$ be a prime number. Consider the word: $w=0^p1^p \in L$.
By the pumping lemma, it can be written as $w=xyz$ where $|y| \geq 1$,
$|xy| \leq a $, $xy^nz \in L \ \ ,\forall n \geq 0$.
Consider $w' = xy^0z$.
Note that the ...
2
Given a normal form grammer $G$ for an infinite prefix-closed $L$, examine the (almost) regular grammer $G'$ obtained by transforming rules of the form $A\rightarrow BC$ into $A\rightarrow B$. I leave it to you to show that $L(G')$ satisfies your requirements.
2
You can write your language as a union of simpler languages:
$$
\{ a^{i+2} b^i : i \geq 0 \} \cup
\{ a^{i+1} b^i : i \geq 0 \} \cup
\{ a^i b^i : i \geq 0 \} \cup
\{ a^i b^{i+1} : i \geq 0 \} \cup
\{ a^i b^{i+2} : i \geq 0 \}
$$
2
In fact this follows from a general property of the star operation. When we start with an arbitrary language $L$ of all strings of certain lengths, then the star $L^*$ of that language is always regular. More precisely:
Let $A\subseteq \mathbb N$, and $L = \{w\in \Sigma^*\mid |w|\in A\}$.
Then $L^*$ is regular.
This is a consequence of a property of unary ...
2
The boundary between context-free and context-sensitive is only determined by one thing: whether or not it can be decided with a nondeterministic pushdown automata.
With respect to grammar specifically, most practical programming languages are almost context-free if not context-free, but the context-free/context-sensitive distinction isn't nearly as ...
2
For a detailed discussion how C as standardized in 2011 (see ISO/IEC 9899:2011 – Programming languages – C) diverges from context freeness you might want to look at Jourdan and Poitier, "A simple, possibly correct LR parser for C11", ACM Transactions on Programming Languages and Systems 39:4 (Aug 2017), article 14. And that one assumes preprocessed ...
2
I let you verify that the submonoid of $(\Bbb N, +)$ generated by $2$ and $3$ is equal to ${\Bbb N} - \{1\}$. It follows that
$$
K = \bigl\{w \in A^* \mid |w| = 2 \text{ or } |w| = 3\bigr\}^* = A^* - A
$$
Now $K \subseteq L$ and $L \cap A = \emptyset$. Thus $K = L$.
1
Indeed, the requirement that the DPDA accepts by empty stack has some "severe" consequences.
Under the standard definitions, an automaton with empty stack is blocked from further computations, as normally one would pop a stack single symbol at each computational step. As a consequence DPDA languages by empty stack are prefix-free: if the accepted ...
1
Regular expressions correspond to a simple recursive definition, which starts with the symbols from some alphabet and extends them with applications of three operators: alternation, concatenation and Kleene closure.
So ask yourself: Which of these operators can produce an infinite set?
Formal definition:
Let $\Sigma$ be a finite set of symbols. Then the set ...
1
We are provided the language :
$$L=\{w| |w| \text{ is prime} \}^*$$
Let us investigate the type of strings in $L$. We see that $L$ has such strings whose length is either zero or can be expressed as a sum of prime numbers. i.e. if $x \in L$ then we have :
$$|x| = \begin{cases}
0 \text{ or}\\
\Sigma p_i \text{ where $p_i$ $\in$ Set of all prime ...
1
You are correct. However we can simplify this a bit: $\epsilon + (a+b)^2(a+b)^*$.
The language is all words with length $\neq 1$. Thanks to @Emil Jerabek and @Nathaniel for pointing this out in the comments! (and correcting me multiple times!)
1
You can use the word $a^pb^p$, where $p$ is the constant promised by the pumping lemma.
1
Here are the first few even natural numbers:
$$
\begin{array}{r}
0 \\ 10 \\ 100 \\ 110 \\ 1000
\end{array}
$$
Here are the first few odd natural numbers:
$$
\begin{array}{r}
1 \\ 11 \\ 101 \\ 111 \\ 1001
\end{array}
$$
Notice any pattern? You take it from here.
1
Let $L = \{a^nb^na^mbba^{3m} : n,m \geq 1 \}$, which is clearly context-free. Then
$$
\operatorname{half}(L) \cap a^+b^+a^+b = \{ a^nb^na^nb : n \geq 1\},
$$
which is not context-free. Hence $\operatorname{half}(L)$ is not context-free.
(If $L$ is a unary context-free language then $L$ is regular, and so $\operatorname{half}(L)$ is regular.)
1
The language $L' = \Sigma^* y\Sigma^*$ is regular and, by the closure properties of regular languages, so is $\Sigma^* \setminus L'$. Then, by the closure properties of context-free languages, $L_2 = L_1 \cap (\Sigma^* \setminus L')$ is context-free (since it can be written as the intersection of a context free language with a regular language).
1
An oracle call is stronger than emulating a TM: it allows you in constant time to solve the task of checking if some $x$ is in the language specified by the oracle.
What you saw didn't use oracle machines, since it proved by assuming towards contradiction: It assumed there is a machine $M$, and showed how to use its code in order to build a new machine $M'$ ...
1
Both $L_1$ and $L_2$ are decidable. Hence, they have algorithms $A_1$ and $A_2$ (respectively) that decide them.
Try to create a new turing machine (algorithm) using the two algorithms $A_1$ and $A_2$.
For example, for the union $L_1\cup L_2$, you can create the following algorithm:
run $A_1$ on the input. If it accepted, then also accept.
else, run $A_2$ ...
1
Let us start by noticing that $X \to a^+$, $Y \to b^+$, $Z \to c^+$. Furthermore, $A \to a^n X b^n$ and $B \to a^m Y c^m$. Therefore $S$ generates words of the following two forms:
$$
a^na^+b^nbc^+ \\
a^+a^mb^+c^mc
$$
You take it from here.
1
No, try to think of a counting argument (i.e, the size of each class) in the following way:
There are $2^{\aleph_0}$ possible words in the language, hence $2^{2^{\aleph_0}}$ total languages. However, the number of turing machines is bounded by the total possible number of words (since you can encode a TM as a string), hence there are at most $2^{\aleph_0}$ ...
1
If $j \neq i$ then either $j < i$ or $j > i$. Hence you can write your language as
$$
\{ a^i b^j : j < i \} \cup \{ a^i b^j : i < j < 2i \}.
$$
It suffices to find a grammar for each of these two languages. Such questions have been asked and answered on this site.
1
I had not the enough reputation in this community to leave a comment on @Umamg's answer; so, I try to complete Umang's answer in mine.
One way to show that the language $L=\{a^p: \text{p is a prime number}\}$ is not context-free is to use pumping lemma for CFLs in the following way:
If $L$ was a CFL, then given an arbitrary long string in this language, say $...
Only top voted, non community-wiki answers of a minimum length are eligible
