# Tag Info

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

15

"I know that this statement is false, but couldn't find an example to disprove it." It might come as a surprise to you that, in fact, every non-context-free language can be a counterexample. We have the following fact, assuming any fixed alphabet $\Sigma$. Let $L$ be a language. Then there exist regular languages $L_1, L_2,...$ such that $L=\cap_{... 8 To add to John L.'s answer, for some intuition: the operations of infinite intersection and infinite union typically do not preserve any properties of languages. In particular, no nontrivial class of languages is closed under infinite union or infinite intersection: not regular languages, not context free languages, not P, not NP, not Turing computable, not ... 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 follows from the pumping lemma, if you examine the proof closely enough. 4 Answer 1: The question is meaningless as written. You are mixing different kinds of notations here that are intended for different purposes. BNF and ABNF are concrete notations for writing the abstract concept of a context-free grammar. "Van Wijngaarden grammar" refers either to an abstract type of grammar a la "context-free grammar", or ... 4 Consider L_n = \{a^2, a^3, a^5 \ldots a^n, a^{n+1} \ldots \}  (only prime length strings over a till the length n, and all strings over a of length greater than n) if n is prime, else L_n = \Sigma^*. Note that each of these L_n is regular (Why?). It’s easy to see that the infinite intersection language would contain the strings over a of ... 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 ... 3 Let the PDA for the given language L be P. Take two copies of states of P: P_1 and P_2. We will join P_1 and P_2 as follows: if there is transition state S from T on reading x pushing/popping Y, then add an \epsilon-transition from S_1 to T_2 pushing/popping Y, and add a transition from S_2 to T_1 on reading x pushing/... 3 This answer assumes that v_i \in \Sigma are individual symbols. You can prove this using closure properties. The advantage is that any class of languages closed under the requisite closure properties will be closed under this operation. Specifically, we will need closure under homomorphism, reverse homomorphism, and intersection with regular language, ... 3 I'll just show how to build a grammar for L_1 = \{ u\#v, |u|_a > |v|_a \}. Then it'll be straightforward to combine 4 similar grammars into a grammar for L. The idea is to write u\#v as xay\#v with x,y,v \in \{a,b\}^* and |y|_a = |v|_a. The construction of y\#v is handled by the non-terminal Z which "grows" it from the center.$$ \...

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

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 Lets assume towards contradiction that L is regular. Then, by closure properties, we have$\bar L$is regular, and thus also$\bar L \bigcap (a^*b^*c^*)$is regular. But calculating it, we find out$\bar L \bigcap (a^*b^*c^*)=\{a^nb^nc^n\}$is not regular. 3 PDAs that are allowed to have more than one initial state (let's call them PDAIs) are computationally equivalent to conventional PDAs: Trivially, every conventional PDA can be considered as a PDAI that happens to have one initial state. Every PDAI can be converted to an equivalent PDA with the process you describe. So yes, PDAIs accept exactly the context ... 3 Maybe you're confusing two different problems. The algorithm you are describing shows that the problem of testing whether a CFG generates some string from$1^∗$is decidable (e.g., see here at page 21). Anyway, the problem of testing whether a CFG generates all the strings of the language$1^∗$is truly decidable. Consider all production rules to be simple (... 3 Construct one PDA for$n=m$and another one for$n=2m$. Branch to one of them using an$\epsilon$transition at the very beginning. 3 Let$A=\{a^nb^n \mid n \in \mathbb{N}\}$. Then we know that$A$is non-regular and context-free. Also we can see that$A^*\cap a^*b^*=A$. Since$a^*b^*$is a regular expression, we do know that it is regular. Lets assume that A* is regular. The regular languagues are closed unter intersection. Therefore$A^*\cap a^*b^*$must be also regular(because we assume ... 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 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 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-...

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