# Questions tagged [context-free]

Questions about the set of languages (equivalently) described by context-free grammars or accepted by (non-deterministic) pushdown automata.

185 questions
Filter by
Sorted by
Tagged with
5k views

### Closure of CFL against right-quotient with regular languages

Let $A/B$ = $\{ w \mid wx \in A$ for some $x \in B \}$. Show that if A is context free and B is regular, then $A/B$ is context free. My interpretation of this is is that we need to show that if a ...
847 views

### Unambiguous but nondeterministic context-free language?

Whenever deterministic context-free languages are discussed, the webpage/textbook would always give a side note saying that although deterministic context-free languages are never ambiguous, ...
3k views

### unambiguous grammar but it's not LR(1)

I have following grammar: $$A \to a A a \mid \varepsilon$$ This grammar is not ambiguous because it has no more than one parse tree from the any sentence generated by this grammar, but there is a ...
1k views

### Tips for creating “Context Free Grammar” [duplicate]

I am new to CFG's, Can someone give me tips in creating CFG that generates some language For example $L =\{ w v w^R \mid v,w\in \{a,b\}^*\wedge|v| \text{ is even } \}$, where $w^R$ is the reverse ...
1k views

### every DCFL has an LR(1), an LALR(1) and even an SLR(1) grammar

Here is one discussion that says, "every DCFL has an LR(1), an LALR(1) and even an SLR(1) grammar." And wiki says, "a language can be generated by an LR(k) grammar if and only if it is ...
3k views

### Is Context Free Language closed under perfect shuffle?

Note that this is not shuffle but perfect shuffle, defined as follows: Let $w = a_{1}a_{2} \ldots a_{n}$ and $x = b_{1}b_{2} \ldots b_{n}$ be two strings of the same length. Then the perfect shuffle ...
5k views

### Is there a context free, non-regular language $L$, for which $L^*$ is regular?

I know that there are non-regular languages, so that $L^*$ is regular, but all examples I can find are context-sensitive but not context free. In case there are none how do you prove it?
420 views

### Constructing all context-free languages from a set of base languages and closure properties?

One way of looking at regular expressions is as a constructive proof of the following fact: it's possible to construct the regular languages by starting with a small set of languages and combining ...
412 views

### How powerful are CFGs that allow an infinite number of rules?

I was wondering recently what would happen if we'd allow context-free grammars to have an infinite number of rules. Clearly, if we'd allow arbitrary such infinite sets of rules, every language $L$ ...