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
