# Questions tagged [formal-grammars]

Questions about formal grammars, generative descriptions of formal languages.

1,109 questions
Filter by
Sorted by
Tagged with
18 views

### how to construct right-linear grammar

I do not succeed in this question: $S \rightarrow Rc\,|\,q_fb\,|\,b$ $R \rightarrow Rc\,|\,q_fa\,|\,a$ $q_f \rightarrow q_fa\,|\,a$ Need to construct a right-linear grammar Would appreciate help :)
39 views

### Checking correctness of grammar for $L = \{w \in \{a, b\}^* \text{ }| \text{ } w \text{ has } n_a(w) = 2n_b(w)\}$

I have written a CFG that supposedly generates $L$ below. $$L = \{w \in \{a, b\}^* \text{ }| \text{ } w \text{ has } n_a(w) = 2n_b(w)\}$$ Where $n_a(w)$ is the number of $a$'s in $w$ and similarly for ...
19 views

### Algorithmically find a formal grammar for a recursively enumerable formal language

The algorithmic problem is as follows. The input is the source code of a program accepting an integer as input and outputting a finite binary sequence. This program defines a recursively enumerable ...
12 views

### Give CFG for the language $L=\{0^i1^j0^j1^i|i,j\geq 0\}$ [duplicate]

Give CFG for the language $L=\{0^i1^j0^j1^i|i,j\geq 0\}$ I have no idea
56 views

### Are decidable set/languages EQUIVALENT to type 1 grammars (non-contracting)?

Suppose a Turing Machine (TM_G) that generates natural numbers following < or, equivalently, it generates words in lexicographical order. Then, that language/set is decidable. Because it is trivial ...
53 views

### Existence of a CFL $L$ such that $\sqrt{L}$ is not CFL

Does there exist a CFL L such that the language defined as $L' = \sqrt{L} = \{w | ww \in L\}$ is not CFL? I feel that there is no such $L$ but obviously, I am unable to prove it. I am sorry but I have ...
11 views

### How do bottom up parser evaluate things that need an inherited attribute?

I learned that Bottom up parsers use only synthesized attributes to evaluate semantics. Which makes sense considering that it would be very hard to evaluate an inherited attribute in bottom up ...
21 views

### Context free grammar transformation to Normal Form

I found a task where you need to transform context free grammar to normal form. I'm a High Shcool student at this moment. But my Brother learning this at the university. He don't have much time to ...