New answers tagged

0

The following grammar generates the language $L = \{ w \in \{a, b\}^*\ | \ \#_a(w) = \#_b(w) \}$. S -> aSbb | ε


1

I think you can do it in this way $$\begin{align} X&\to A\ |\ aXc\ |\ aAc\\ A&\to aA_t\\ A_t&\to aA_t\ |\ B\\ B&\to bB_t\\ B_t&\to bB_t\ |\ \epsilon\\ \end{align}$$ Here $X$ can choose to do the first transformation, if there are not going to be any $c$s. $X$ can do the second transformation many times to add an initial chunk of the same ...


0

LL(1) grammars must be unambiguous, have no left recursion, and no conflicts. The grammar you provide is unambiguous in terms of the syntax tree, however there are conflicts when parsing (which stops it from being an LL(1) grammar). The conflicts reside in the first set of S and C. That is to say, FIRST(S) = { b }, but its ambiguous in which production rule ...


1

$\{ww\mid w\in\{0,1\}^*\}$ not being context-free does not imply every subset is also not context-free. In this case, $0^n1^n0^n1^n$ passes the pumping lemma, since it can be written as follows $0^p1^p0^p1^p=0^p1^{p-1}1^n0^n0^{p-1}1^p$.


2

The idea is to replace a single transition by a sequence of transitions. Suppose for example that $h(\sigma) = \tau_1 \ldots \tau_\ell$, and consider a transition at state $p$ which replaces the symbol $A$ on the stack with the string $\alpha$, and moves to state $q$. We replace this transition by a sequence of transitions $p \to s_1 \to \cdots \to s_{\ell-1}...


0

Consider the string $abab$. There are two ways to generate this string: $S \rightarrow abSb \rightarrow abab$, and $S \rightarrow aAb \rightarrow abSb \rightarrow abab$. Therefore, the grammar is ambiguous. To find the unambiguous grammar corresponding to this one, start by thinking about the kind of strings this grammar can generate. Also, consider not ...


0

Your simplification is wrong. The language of the first grammar includes $b$, but the one of the second grammar does not. If you replace the definition of $A$ in the productions of $B$ you obtain $B \to b \mid \epsilon$. Then if you replace $A$ and $B$ with their definition in $S$ you have. $$ S \to a \mid bb \mid b \mid aba \mid aa $$


0

The context free language at the top seems to be empty, as there always will be a variable at any time while trying to derive a word! (this is because every transition is from a variable to some a few letters and at least one variable)


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


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


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


3

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


2

Not sure if this answers your question, but I will contribute two details regarding lexing/parsing ambiguities in C in general. I hope these are still helpful. Consider the expression T ** c;. Since C supports type declarations via typedef, the parser itself cannot decide whether this is multiplication with variables T and *c or a variable declaration of a ...


1

Here's an intuitive explanation: It follows essentially from the nature of LL(1) parsers: LL(1) parsers build a LL(1) parsing table. The rows of the table are nonterminals, and the columns are terminals. We can think about LL(1) parsing as doing LL(1) table lookups upon encountering each symbol in the input: we look at the entry determined by the current ...


0

If $L$ were context-free then so would $L' = d(L \cap (0+1)^*\#(0+1)^*)$ be, where $d$ is the homomorphism that deletes $\#$. However, $L'$ is the language of squares (words of the form $w^2$), which is well-known not to be context-free. If for some reason you have to prove that $L$ is not context-free directly using the pumping lemma, this suggests looking ...


0

Perhaps it can be proved using Ogden's Lemma and its generalization by Bader and Moura, this is a rather informal sketch of the proof. First restrict $L$ to strings of length $4n$ and apply to it the following homomorphism between $\Sigma = \{ 0,1 \}$ and $\Sigma' = \{ a, b, c\}$: $h(11) \to a$ $h(00) \to b$ $h(01) \to c$ $h(10) \to c$ If $L$ is CF then also ...


2

Actually the example of a language not accepted can be quite simple, due to a technicality. The language $a^*$ is not generated by a s-grammar. In fact, an s-grammar cannot generate $\varepsilon$. In order to remove $S$ from the stack we have to apply at least one production, and any production will produce a terminal symbol. But even if we see this as a ...


0

A unary language $L$ is context-free iff it is regular iff it is eventually periodic, that is, if the set $N = \{n \in \mathbb{N} : a^n \in L\}$ satisfies the following property: there exist $m \geq 0$ and $r \geq 1$ such that for all $n \geq m$ we have $n \in N$ iff $n + r \in N$. In particular, any unary language which has zero limiting density (i.e., $\...


0

If you could bound the stack height, say to some constant $c$, then it would have been possible to define an NFA for the task: Simply encode in the NFA states another $c$ values that represent the current values in the stack (by defining $\hat Q=Q\times\Sigma^c$. The rest i will leave to you) This would contradict the non-regularity of this language, and ...


Top 50 recent answers are included