19

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 ...


16

The language consisting of the words $w_1,w_2,\ldots,w_n$ is generated by the context-free grammar $$ S \to w_1 \mid w_2 \mid \cdots \mid w_n. $$


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 ...


7

The intersections of context-free languages will never reach the full family of context-sensitive languages. The class of languages expressible as the intersection of $k$ context-free languages is shown to be properly contained within the class of languages expressible as the intersection of $k + 1$ context-free languages. Hence an infinite hierarchy of ...


5

One endmarker is insufficient to prove this. Instead, we must use multiple endmarkers. Here's the full proof, with the same basic idea taken from the other answer. Using the notation from Sipser 3rd edition problem 5.21, let the string pairs $(t_i, b_i)$ for $i \in \{1, 2 \ldots k\}$ be an instance of the PCP problem. Define grammar rules $T \rightarrow t_i ...


5

Your grammar doesn't seem to generate $caac$. Indeed, in order to generate this work, a simple case analysis shows that the derivation must start $$ S \to cYc \to caYYc, $$ at which point it is clear that we cannot generate $caac$. I assume you know how to generate the language $c\Sigma^*c$, as well as the language of all words with an equal number of $a$-s ...


5

For every symbol $\sigma_i$ that the PDA reads, it guesses a symbol $\tau_i$. It simulates the DFA on the word $\tau_1 \ldots \tau_i$, and will only accept if the DFA accepts. Using the stack, it maintains the following counter: $$ (\#_a(\sigma_1 \ldots \sigma_i) - \#_b(\sigma_1 \ldots \sigma_i)) - (\#_a(\tau_1 \ldots \tau_i) - \#_b(\tau_1 \ldots \tau_i)), $...


5

Clearly we cannot keep both the number of $a$'s and the number of $b$'s on the stack, because what order should we use. The solution (I think) is to keep the difference of these numbers on the stack. Or better, the difference between the promised numbers in the DFA computation on word $x\in L$ that we guess, and those that are realised by the (permuted) word ...


4

This question shows the pitfalls of applying algorithms without understanding how they work. There is absolutely no problem with applying an algorithm mechanically, but in that case, you should make sure that the algorithm you are applying is 100% correct, and that you are following it 100% accurately. How does the $\epsilon$-removal work? Suppose that we ...


4

Let $\Sigma' = \{\sigma' : \sigma \in \Sigma\}$ be a tagged version of the alphabet of $\Sigma$. Let $L'$ be a version of $L$ obtained by tagging all letters. Let $h\colon \Sigma \cup \Sigma' \to \Sigma$ be a homomorphism which removes tags. Then $$ L^{|2|} = h(LL' \cap \{xy : x \in \Sigma^n, y \in \Sigma^{\prime n} \text{ for some } n\}). $$ Standard ...


4

In order for their example to work, the authors need identifiers to be of unlimited length. This is because the language $$ \{ wcw : w \in \{a,b\}^*, |w| \leq n \} $$ is context-free (indeed, regular). The syntax of a language like Pascal or Algol is context-free. This accomplished by waiving the requirement that an identifier be declared before its usage; ...


4

It looks like by describing your "CFG+" grammar, you have independently reinvented/rediscovered the conjunctive grammar. Here is more quote from that article on Wikipedia. The family of conjunctive languages is closed under union, intersection, concatenation and Kleene star, but not under string homomorphism, prefix, suffix, and substring. Closure ...


4

A word in $L$ must either be of the form $b^i a^j$ with $i \neq j$ or it must have $ab$ as a substring. Therefore you can write a context-free grammar $G$ for $L$ as the union of two context-free grammars $G_1$ and $G_2$ for $L_1 = \{b^i a^j \mid i \neq j\}$ and $L_2 = \{w \in \{a,b\}^* \mid ab \mbox{ is a substring of } w\}$. It is easy to come up with a ...


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

Your problem can be formalized in several equivalent ways: Given a context-free grammar $G$ over $\Sigma$, is $\overline{L(G)} := \Sigma^* \setminus L(G)$ context-free? Given a PDA $M$ over $\Sigma$, is $\overline{L(M)}$ context-free? Since we can effectively (and efficiently) translate between the two representations, both problems are equivalent. We ...


3

In the general case, your grammar generates more words than those in $L^*$. Consider this grammar: $$ \begin{array}{l} S \to A \\ A \to (S)\ |\ a \end{array} $$ The above grammar generates $L = \{ a, (a), ((a)), \ldots \}$. Using Kleene's star, we get $L^* = \{a,aa,a(a), ((a))(a), \ldots \}$. Note that $(aa)\notin L^*$. However, if we add your ...


3

Your clam is false even in the special case where $L_1 \cap L_2$ is regular. To construct a counterexample let $L_1$ be a language that is not context free (e.g., $L_1 = \{a^n b^n c^n: n \ge 0\}$) and pick $L_2 =\emptyset$ (other choices for $L_2$ work too). Both $L_2 = \emptyset$ and $L_1 \cap L_2 = \emptyset$ are regular (and hence also context-free), ...


3

Let $c(w)=2\#_b(w)-\#_a(w)$. Your language is exactly $\{w\mid c(w)=0\}$. Now consider a string $w$ with $c(w)=0$ and $|w|\ge 2$. If we can split $w$ into three parts: $w=pms$ such that $c(p)$ and $c(pm)$ have different signs, i.e., $c(p)c(pm)<0$, then there are two cases: $c(p)>0$ and $c(pm)<0$. Note each time we append a character to string $x$, $...


3

The unequal number of $a$'s and $b$'s have {equal number of $a$'s and $b$'s} with {{extra $a$'s } or {extra $b$'s}} Extra $a$'s or extra $b$'s can be at the beginning at the end in between (ANY WHERE) and any number of times Let $P$ derive strings with extra $a$'s Let $Q$ derive strings with extra $b$'s Let $X$ derive equal number of $a$'s and $b$'s Let $A$...


3

As HendrikJan stated, we can for example obtain the following languages with above CFG $$01, 0001,\dots$$ which do not meet the required conditions. Instead, we need to make sure that the ends are always the same. We can do that by the following production rules. $$ S\rightarrow 0S0$$ $$S\rightarrow 1S1$$ $$S\rightarrow \epsilon$$


3

The set of all regular languages is a subset of context free languages. So if you have a context free grammar (CFG) that generates a regular languages, you most certainly can convert it to a regular expression (RE), regular grammar (RG), or finite automata (FA). Before I go further with your example, I will simplify it so that we only deal with 3 terminals (...


3

If a word is not of the form $w\#w$ then one of the following must happen: It contains no $\#$. It contains more than one $\#$. It is of the form $x\#y$, where $x,y \in \{0,1\}^*$ and $x \neq y$, in which case one of the following must happen: $|x| > |y|$ or $|x| < |y|$. $x_i = 0$ and $y_i = 1$ for some $i$, or vice versa. The only case which is non-...


3

The PDA first guesses whether $m=n$ or $n=k$. According to the guess, it either just checks that $m=n$, or just checks that $n=k$. What your heuristic argument suggests is that this language cannot be accepted by a deterministic PDA. You can likely show this by adapting the proof here.


3

Suppose that $w$ is in the language. We can write $w$ as a concatenation of runs: $$ w = a^{i_1} b^{j_1} a^{i_2} b^{j_2} \dots a^{i_m} b^{j_m}, $$ where all indices other than possibly $i_1,j_m$ are strictly positive. A word of this form belongs to $(a^nb^n)^m$ if all indices are equal. Since $w$ is in the language, there must exist two indices which are ...


3

Condition 3 as in the question, "$\forall i >0, \exists z= uv^iwx^iy \in L$" does not make sense. It should be "$uv^iwx^iy \in L\text{ for all } i\ge0$", i.e., $uv^0wx^0y=uwy$, $uv^1wx^1y=uvwxy$, $uv^2wx^2y$, $uv^3wx^3y$, $uv^4wx^4y$, and so on are in $L$. Please note the first word, $uwy$, where $v$ and $x$ do not appear, i.e, we &...


3

It's true. If the CFG is not null free, and the input sentence is not null, you can remove the null from the CFG and then parse the input sentence with the resulting grammar. You already know how to do that in cubic time. If the CFG is not null free, and the input sentence is null, you can immediately tell whether the input sentence is accepted by the CFG.


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 ...


3

As you have noticed, you can decompose between words of odd length and words of even length. Since the odd part is quite easy, I will focus on the even one, that is $L = \{uv \mid u, v\in \{0,1\}^*\wedge u\neq \mathrm{complement}(v)\}$. Given $u, v\in\{0,1\}^*, |u|=|v|$, if we write $u = u_1…u_k$ and $v = v_1…v_k$, then $uv \in L$ if and only if $k \geq 1$ ...


3

You can use the pumping lemma to show that this language is not context-free. Suppose it is context-free and let $n$ be the constant of the pumping lemma. Consider the word $u = a^nb^nc^nd^{3n}$. $u$ can be written $u = vwxyz$ with: $|wxy| \leq n$ $|wy| > 0$ $\forall k \in \mathbb{N}, vw^kxy^kz\in L$. Now using the first condition, $wxy$ can be written ...


3

Appearance checking is a concept in the theory of regulated grammars. In an ordinary (context-free) grammar we may appay a production to a string if its right-hand side occurs in that string. So for $\pi: A\to \alpha$ we write $x \Rightarrow_\pi y$ if $x= w_1 A w_2$ and $y = w_1\alpha w_2$. In a regulated grammar we may specify the order in which the ...


Only top voted, non community-wiki answers of a minimum length are eligible