# Tag Info

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