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