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 ...
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 ...
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}...
1
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 (...
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 ...
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$.
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 ...
Only top voted, non community-wiki answers of a minimum length are eligible
