# Questions tagged [formal-grammars]

Questions about formal grammars, generative descriptions of formal languages.

1,023 questions
Filter by
Sorted by
Tagged with
36 views

### Explain why a language can be generated by a context free grammar [duplicate]

I have a problem where I am asked to explain why the language that has words made of $a$ and $b$ such that the number of $a$'s is equal to the number of $b$'s, can be generated by a context free ...
352 views

### Deciding whether a context-free grammar's language is empty

Consider the formal problem: Given a context-free grammar $G$, is the language $L(G)$ empty? Can we determine if the problem is recursively enumerable, recursive, in NP, or in P? Can the entire ...
35 views

### Find any kind of grammar for the language

Find any kind of grammar for the language L = {w ∈ Σ* | in w there are twice as many a's than b's} and reason its correctness. Where ...
46 views

### Is there a regular grammar for the language $\{ w : |w|_0 = |w|_1 \}$? [duplicate]

I need to prove whether the language $L = \{w \in \{0,1\}^* \mid |w|_0 = |w|_1 \}$ can be written as a regular grammar. Obviously it can, but how do I prove it?
443 views

31 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$, ...
254 views

### Proof of completeness for CFG having twice as many zeroes as ones [duplicate]

One possible CFG containing twice as many zeros as ones can be, S -> 0S0S1S | 0S1S0S | 1S0S0S | ϵ (This CFG is redundant but it will do the job. So I am not interested in the redundancy. Other ...
259 views

### Writing context free grammar

I have the following language: {0m1n0n1m | m,n ≠ 0} I was wanting to write Context-free grammar for it. I'm a little confused because the rule doesn't mention that m and n are not equal to each ...
79 views

### Growing context-sensitive grammars with context-free rules

Has anyone ever considered the class of languages $X$ generated by growing context-sensitive productions which are described by context-free rules? In particular, I wonder if there is a NP-complete ...
60 views

### How to check if my language is context-free can't seem to solve it using pumping lemma

I have a language and I am trying to see if it's context-free or not, by trying to use a pumping-lemma but I can't figure it out, been reading a lot of other posts but still struggling to apply it to ...
570 views