# Tag Info

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

2

Unfortunately your grammar generates only $\epsilon$ (which is not in the language, since $n$ and $m$ are greater than 0), as you don't delete the $A$; moreover you don't control that the number of $A$'s is thrice the numeber of $C$'s. You can try something like this: $S\rightarrow aaaS'c$ $S' \rightarrow aaaS'c | B$ $B\rightarrow Bb | b$

2

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

2

This language L = { w | w has equal number of as and bs and w≠ ε (since you put a +) } is a CFL A PDA would work as follows : On reading a : If the stack is empty or the top of the stack is a push a If the top of stack is b pop b push nothing On reading b : If the stack is empty or the top of the stack is b push b If the top of stack is a pop a push nothing ...

1

Take unambiguous grammars for L and R with start symbols $S_L$ and $S_R$. For L union R take a grammar that starts with $S->S_L$, $S->S_R$. Since no string is both in L and R, only one of the initial two rules can succeed, so the grammar is unambiguous.

1

Consider a context-free grammar $\mathcal{G}$ for $L(A)$ in Greibach normal form with no useless nonterminals (i.e., non-terminals that cannot be transformed into a sequence of only terminals by applying production rules). Such a grammar can be mechanically constructed from $A$. Now build a directed graph $G = (V,E)$ as follows: Each nonterminal of \$\...

1

It's actually a property of the "singleton match strategy" usual in naive implementations of recursive descent parsers with backtracking. I'll quote this answer by Dr Adrian Johnstone: The trick here is to realise that many backtracking parsers use what we call a singleton match strategy, in which as soon as the parse function for a rule finds a ...

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