# Tagged Questions

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

5 views

### LL(k) vs Strong LL(K)

What is the diference between LL(K) and strong LL(K) grammars definitions? LL(k): For every pair of production rules A→α and A→β the following condition holds. FIRSTk(αy) ∩ FIRSTk(βy) = ∅ ...
38 views

### Proving that a CFG generates a language [duplicate]

Is a suitable way to prove that any given CFG generates (or not) any given language to draw its total language tree? What if the tree is infinite? What would then be a better way to prove that a ...
51 views

### Which programming languages can be described by deterministic context-free grammars?

This question asks which programming languages have a syntax that cannot be described by deterministic context-free grammars - the answer is "Many [...] including Algol 60, C, and C++". Until ...
170 views

52 views

### Is converting an ambiguous grammar to an unambiguous grammar computable?

Is the problem of converting ambiguous grammar into unambiguous grammar computable? (Consider Domain as all context free languages).
37 views

### Find a CFG for palindromes with at most three c's

I'm trying to figure this one out, as I've found the CFG for the palindrome language. I can't work on a solution that also covers #c(w) <= 3. Find a CFG for the language {w∈{a,b,c} | ...
40 views

### If I prove that a language is not a CFL, can I assume it is Turing-Decidable?

Lets say I have just used the pumping lemma to prove a certain L language is not CFL. If it is not CFL can I use that as a proof that it is Decidable? Or is this not enouph and I still have to ...
75 views

### Finding Language of a CFG

Say you are given the following CFG $G$: $$S \to S_1 \mid S_2 \\ S_1 \to AbAS_1c \mid \epsilon \\ S_2 \to BaBS_2c \mid \epsilon \\ A \to Aa \mid \epsilon \\ B \to Bb \mid \epsilon$$ What is $L(G)$? ...
29 views

72 views

### CFG Equivalent of regular expressions

So I was wondering something about the Chomsky hierarchy. DFAs (and NFAs) accept regular languages, while NPDAs accept context-free languages. Right-regular or left-regular grammars produce regular ...
83 views

### Is intersection of regular language and context free language is “always” context free language

I have read that intersection of regular language and context-free language is always context-free. Most of the places an standard example has been used to prove this, e.g., \begin{align*} L_1 &= ...
27 views

### Preservation of context-free languages under prefix and suffix elimination

Let $\Sigma=\{0,1\}$ be our alphabet. Let $L$ be some context-free language, which is known to start and end with 0's, meaning that every word $x$ in $L$ has a form $x=0y0$. Let $M$ be a language ...
36 views

### Languages reducible to and from context-free

Let $L'$ be a context-free language. If $L \leq_M L' \leq_M L''$, where $\leq_M$ denotes mapping reducibility (aka many-one reducibility), what can we know about $L$ and $L''$? I think they're both ...
52 views

### Why DCFL is not closed under kleene star?

I have read somewhere that DCFL is not closed under kleene star. but I haven't found any example
90 views

### Union of a Deterministic Context-free language and a Regular Language is a Deterministic Context-free Language

In formal language theory, deterministic context-free languages (DCFL) are a proper subset of context-free languages. They are the context-free languages that can be accepted by a deterministic ...
28 views

### Lossless Condensing, Modification, and Decondensing

Given a string $\alpha$ that is derived from context-free grammar $G$, what is an algorithm $f$ such that there exists a string $\beta$ (derived from an unrestricted grammar) where $f(\alpha)=\beta$,...
33 views