# 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
767 views

### Do NPDA work in parallel?

Assume my language is $$L= ww^{r}\$$ Now when we use NPDA for this,we will guess middle every time. It may be actual middle or it may not, so a new branch is created every time as I have a choice ...
3k 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 ...
257 views

### Figuring out the language of a non-linear CFG

I have the CFG G with the following production rules: $$S \to aSaS \mid b$$ Is it possible to find $L(G)$? I have no idea how describe it by any pattern. I use grammophone to check example words, ...
366 views

### Inducing a context free grammar [closed]

I have a file containing a subset of possible strings from a context free language. I am looking for a mechanism to induce the grammar from this information. Is that possible?
527 views

### How to check for ambiguous grammar if you don't know the string

Let's say I have a CFG grammar $G$ which describes some rules for language generation. How can you tell that grammar can generate ambiguous results for a string if you don't know that string? I know ...
2k 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
311 views

2k views

### CFG for the language “number of a's = number of b's + 2”

How can I construct a context-free grammar for the following language? $$L = \{ w \in \{a,b\}^* : \#_a(w) = \#_b(w) + 2 \}.$$ Please help me out in this. I am not sure how to approach this ...
3k views

### Is an inﬁnite union of context-free languages always context-free?

Let $L_1$, $L_2$, $L_3$, $\dots$ be an inﬁnite sequence of context-free languages, each of which is deﬁned over a common alphabet $Σ$. Let $L$ be the inﬁnite union of $L_1$, $L_2$, $L_3$, $\dots$; i....
390 views

### Why does $A(L)= \{ w_1w_2: |w_1|=|w_2|$ and $w_1, w_2^R \in L \}$ generate a context free language for regular $L$?

How can I prove that the language that the operator $A$ defines for regular language $L$ is a context free language. $A(L)= \{ w_1w_2: |w_1|=|w_2|$ and $w_1, w_2^R \in L \}$, where $x^R$ is the ...
353 views

### Why is the following language not context-free?

$L = \{a^n b^m | m \not= n^2 \}$ I guess I need to use Pumping Lemma for CFL in order to prove this. But I'm stuck. Assuming that $a^n b^m = uvxyz$, we know that $v$ or $y$ can not have both $a$ ...
7k views

### Give CFG and PDA for the words that start and end with the same symbol

I need to give a PDA and CFG for a language that contains all binary strings that start and end with the same symbol. I've created the CFG with no problem, but I'm stuck with the PDA and don't quite ...
186 views

### Language of the graph of an affine function

Write $\bar n$ for the decimal expansion of $n$ (with no leading 0). Let : be a symbol distinct from any digit. Let $a$ and $b$ ...
243 views

7k views

1k views

4k views

### Prime number CFG and Pumping Lemma

So I have a problem that I'm looking over for an exam that is coming up in my Theory of Computation class. I've had a lot of problems with the pumping lemma, so I was wondering if I might be able to ...