# Questions tagged [formal-grammars]

Questions about formal grammars, generative descriptions of formal languages.

1,251 questions
Filter by
Sorted by
Tagged with
1 vote
257 views

### How to remove ambiguity from the grammar?

I want to remove ambiguity from the grammar below: S → ABC A → abA | ab B → b | BC C → c | cC I have removed left recursion and left factoring and obtained the grammar as follows: S → ABC A → abA' A' →...
62 views

### Why the Following Grammars Are Not in CNF

I am reading the book "Automata, Formal Languages, and Automata" written by Dr. Emre Sermutlu and in page 153, it is stated that the following grammars are not in Chomsky Normal Definition (...
1 vote
127 views

### How does ANTLR4 handle optional rules?

Are the following two stat rules equivalant? stat : 'if' expr 'then' stat ('else' stat)? ; ...
18 views

### The maximal choice smallest grammar algorithm. Is this an exact algorithm or an approximation?

When we speak of a variable, sometimes we will mean the string it expands to, and other times, the variable itself. Let $t \leqslant s$ mean substring. Take the string $s = a^6$. Then its ...
33 views

54 views

### prove that the unique language $A$ such that $AB$ is context free for all languages B is the empty set

Prove that the unique language $A\subseteq \Sigma^*$ such that $AB$ is context free for all languages $\subseteq \Sigma^*$ is the empty set. If $A$ is not the empty set, there should be a way to ...
302 views

### What are the languages produced by context free-grammars with backspace?

If we add backspace to the output alphabet, are all the languages produced still context-free? (If not, then what are they?) The word (a, b, c, Backspace, Backspace), for example, gets interpreted as ...
49 views

### Proving grammar equivalence in simple grammar (generate any sequence of three characters)

Goal is proving grammar equivalence Upper-case symbols are non-terminal. Lower-case symbols are terminal. The start symbol is S. A grammar production rule is non-...
1k views

### Is it always possible to order grammar rules so that all the symbols on the left will be contained on the right in a previous rule?

This is about unrestricted grammars Assume S is the start symbol. Assume 1 and 0 are ...
1 vote
421 views

### Prove a subset of a regular language is regular, context-free but not regular or not context free

I've been tasked with solving this problem, but I'm not sure where to begin: Let $L$ be a context-free language. $L'$ contains all the words that belong to $L$ which can't be defined as $z=uvwxy$, ...
159 views

### Formal language rewrite rules: strange notation

I'm reading "Program=Proof" by Samuel Mimram, and they use a notation for defining a formal language that I'm not familiar with. Here is how "Program=Proof" defines a formal ...
1 vote
413 views

### How to prove the language of words $a^ib^jc^k$ where $\min(i,j)\le k\le\max(i,j)$ is not context-free?

I want to prove that $\mathcal M =\{a^ib^jc^k \mid \min(i,j)\le k\le\max(i,j)\}$ is not a CFL. Using the pumping lemma, let $p$ be the constant, then I choose $w=a^pb^pc^p$. When I separate to cases, ...
1 vote
70 views

### is there a non-context free language A such that A1 is context free?

Is there a non-context free language A over the alphabet $\{0,1\}$ such that $A1 := \{a1 : a\in A\}$ is context free? I was thinking of the language $A = \{0^n 1^{n-1} : n > 0\}.$ Unfortunately, ...
1 vote
71 views

92 views

### Prove or disprove that $\{xc o(x) :x \in A\}$ is context-free, where A is a regular language

Suppose o is a map on strings to strings. For every language R, we let $o(R) := \{o(x) : x \in R\}$. If o(R) is a regular language for every regular language R, then prove or disprove that the ...
398 views

### Find a Context-Free Grammar for $L = \{a^wb^xc^yd^z | w + x = y + z\}$

I have to find a CFG for the given expression: $L = \{a^wb^xc^yd^z | w + x = y + z\}$ This is what I've tried so far: S -> aSd | B | ϵ B -> bBc | ϵ It works for expressions like: aabcdd, ...
75 views

### expression/pattern for language where product of number of 0s and 1s is even

I am trying to solve one of the sample test problems in which I have to write an expression/pattern for the following language: $\{w \in \{0, 1, 2\}^*: {\#}_{0}(w) ∗ {\#}_{1}(w) \text{ is even}\}$ I ...
112 views

### find LR(1) items of the first state

I need to calculate the LR(1) items of the following grammar: S -> E E -> E + T E -> T T -> ID T -> ( E ) I can not even calculate the first group {[...
470 views

### LR(1) grammar that can not be transformed an LL(1) grammar

Looking for an example of a LR(1) grammar that can not be turned into an LL(1) grammar that parsers the same language.
### Is the language $L = \{{a^{2n+1}b^{m+2}a^n | m \neq 2n}\}$ context-free?
$L = \{{a^{2n+1}b^{m+2}a^n | m \neq 2n}\}$ I tried to split $L$ in 2: when $m > 2n$ and $m<2n$, however both resulting languages are not context-free, so I did not find out anything about $L$. ...