18
No. If a language is context-free, it has a BNF grammar, by definition. A context-free language is a language with a context-free grammar, and a context-free grammar is a grammar written in BNF with only one symbol on the left-hand side of each production. That's what "context-free" means.
It might not be convenient to write the grammar. For ...
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 ...
4
First, figure out what the language is.
Then, try to do a few examples of productions in the grammar. What do you notice about the derivation trees and sequences? How would this help you to prove this grammar is unambiguous?
Hint: At each step in the process of deriving a word, what are the possible derivation rules you can use? How would each of them affect ...
3
Yes, and this works for regularity and decidability as well! (not that this is very helpful in any sense)
For example, take any problem $A$ such that $A$ and its complement $\overline{A}$ are not CFLs (the halting problem as an extreme example)
Their union is $\Sigma^*$ which is obviously a CFL.
As a side note, and thanks for @D. Ben Knoble for pointing ...
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
The intersection of two CFL may or may not be a CFL. We can show that both possibilities exist. For example if both $L_1$ and $L_2$ are regular then $L_1∩ L_2$ is regular and therefore CF.
For intersection of non-context-free languages be context-free, you can assume that the intersection could be empty.
2
Let $L$ be an arbitrary language. Then
$$ \{ 0x : x \in L \} \cap \{ 1x : x \in L \} = \emptyset. $$
2
The statement itself doesn't imply that. It just means that the intersection of two DCFLs might or might not be a DCFL; and thus presumably could be a DCFL; could be a CFL but not a DCFL; or could be not context-free.
However, we know more actually.
The intersection of two DCFLs could be, of course, a DCFL. For example, you can let both of them be the same ...
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
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
$$𝑆 → YX \ | \ Y \\
Y → Ab \ | \ b \\
X → ABX \ | \ AB \\
A → SB \ | \ BS \ | \ a \\
𝐵 → 𝐴𝑆 \ | \ d$$
At first I say which rules have a left recursion, considering that the middle tree which is A(the one that A node is the root) has not called itself in its children from the beginning of the left of each child so there is no left recursion in tree ...
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
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
If a word is not of the form $(a^nb)^n$ for $n > 0$, then one of the following must happen:
The word is not of the form $(a^*b)^+$, i.e., it is either empty or ends in $a$.
The word is of the form $a^ib(a^*b)^*a^jb(a^*b)^*$ for some $i \neq j$.
The word is of the form $a^nb (a^*b)^k$, where $n \neq k+1$.
Each of these can be checked by a PDA or ...
1
If you are trying to convert the grammer into Chomsky Normal Form, consider applying this algorithm that can create a new normal grammer from an existing non-normal one.
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
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
The main observation is that every word generated by $Y$ starts with $b$.
Consider a word $w$. If it starts with $a$, it must have resulted by applying the rule $X \to aX$. Otherwise, it must have resulted by applying the rule $X \to Y$. In other words, if $w = a^n b z$, then the derivation must start by applying $n$ many times the rule $X \to aX$, and then ...
Only top voted, non community-wiki answers of a minimum length are eligible
