# Questions tagged [formal-grammars]

Questions about formal grammars, generative descriptions of formal languages.

1,251 questions
Filter by
Sorted by
Tagged with
1 vote
1 answer
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' →...
0 votes
1 answer
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 (...
• 143
1 vote
0 answers
127 views

### How does ANTLR4 handle optional rules?

Are the following two stat rules equivalant? stat : 'if' expr 'then' stat ('else' stat)? ; ...
• 9,501
0 votes
0 answers
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 ...
0 votes
0 answers
33 views

0 votes
1 answer
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 ...
4 votes
1 answer
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 ...
• 181
0 votes
1 answer
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-...
3 votes
2 answers
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
1 answer
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$, ...
2 votes
1 answer
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
3 answers
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, ...
• 239
1 vote
1 answer
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
1 answer
71 views

0 votes
1 answer
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 ...
0 votes
3 answers
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, ...
-2 votes
1 answer
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 ...
0 votes
1 answer
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 {[...
• 3
0 votes
2 answers
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.
• 237
2 votes
0 answers
76 views

### 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$. ...
-3 votes
1 answer
266 views