# Questions tagged [formal-grammars]

Questions about formal grammars, generative descriptions of formal languages.

940 questions
Filter by
Sorted by
Tagged with
17 views

129 views

### Prove the grammar S → S + S | S / S | 10 | 11 | … | 19 is ambiguous

How to prove the following grammar is ambiguous? S → S + S | S / S | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19
72 views

### Context-free Grammar Exercise

Could someone explain me how to form a context-free grammar with all rules R by this example language, please? \begin{equation} L:=\left\{w c v c \overleftarrow{w} | w, v \in\{a, b\}^{+}\right\} \end{...
142 views

### Give a grammar for a language on Σ={a,b,c} that accepts all strings containing exactly one a

I have created the following solution but its left recursive: S--> a|bSc|cSb|Sbc Also it is not accepting: "ab" or "cba" or "abb" or abc. Somebody please guide me. Zulfi.
25 views

### Creating a parse tree from two productions

How can I create a parse tree from the two productions below \begin{align} S &\rightarrow 0S2\mid 0T\\ T &\rightarrow 1T\mid\epsilon \end{align} ... to show how 0012 has been made?
25 views

### Useless production

Kindly consider the following productions. How can I identify a useless production? S->aS|A|C A->a B->aa C->aCb Somebody please guide me. Zulfi.
33 views

### How to convert the left recursive grammar into right recursive grammar

I have a grammar: $A\rightarrow Aa|bB|c$ The above is the left recursive grammar. I understand that I have to remove the string "Aa" from the above grammar or to convert it into the form "aA" to ...
146 views

### Proper algorithm for resolving ambiguity in grammars via enforcing associativity and precedence rules

I was told there is a algorithm that always resolves ambiguity for grammars that have issues with precedence and associativity. I know ambiguity in general is undecidable, so I only want to resolve ...
24 views

41 views

### Does every regular language have a linear grammar?

Some definitions and facts (from Wikipedia): A linear grammar is a context-free grammar that has at most one nonterminal in the right hand side of each of its productions. the left-linear or left ...
18 views

### Use the pumping lemma for context free languages to prove L = {w#w | w \in {a,b}*} is not context free

I know the basics of using the pumping lemma for CFG to prove a language L is not context-free, however, the # symbol seems to be throwing me off or my understanding is not complete.
20 views

### question about LL(1) and LR(0)

If grammar is an $LL(1)$ and does not contain any null production (i.e $V \rightarrow \epsilon$) then does that grammar necessarily be an $LR(0)$ grammar? I have tried to find counterexample for ...
253 views

22 views

### Confused about substitution in grammar in certain cases

To illustrate my confusion let's say I'm given this unambiguous grammar in BNF: ...
29 views

### How to intuitively come up with an example for an ambiguous grammar and how to make that grammar unambiguous?

I don't get how to intuitively come up with an example for an ambiguous grammar. Let's take as an example this grammar: ...
51 views

### Converting S->aTbS|epsilon T->aTb|epsilon to chomsky normal form

The grammar have the following producitons, \begin{align} S&\rightarrow aTbS \mid\epsilon\\ T&\rightarrow aTb\mid\epsilon \end{align} Already turned this homework in, but I need to convert ...
38 views

### An example of a context-sensitive grammar for a given language

Consider this language: $L = \{a^nb^ma^nb^m \mid n,m \ge 1\}$. Can we give for this language a context-sensitive grammar?
25 views

### Does BNF terminate on a first match?

I know that the grammar <expr> = <expr> + <expr> | <num> <num> = 0|1 is ambiguous because it cannot decide between (1+1)+1 or 1+(1+...
29 views

### How to determine valid handle for given bottom up parser?

I came across following question: Consider the grammar: $E → E + n\text{ | }E × n\text{ | }n$ For a sentence n + n × n, the handles in the right-sentential form of the reduction are (...
39 views

### How to find a context-free grammar from a difficult language? [duplicate]

Some Languages are trivial to find their respective context-free grammar. Like for example $L= \{a^nb^n: n \geqslant 0\}$. However some are really difficult to solve. I would like to have some advice ...
19 views

### How do we formally regard a function that takes a lookup set as a parameter?

I have a function that takes a set as a parameter. The function $\phi$ maps a general $x \in R$, where $R$ is a commutative ring with $1$, to a $\phi(x) \in \Bbb{N}$ representing the "grammar size" ...
46 views

### Constructing a DFA of strings that are in A but not in B

I am tasked with creating a DFA for the regular language L = A/B, which are the strings that are in A but not in B. The alphabet is Σ = {a,b,c} I am not really sure where to even start with this one, ...
109 views

### Pushdown Automata - constructing a PDA to recognise a language with at least as many as as bs

I am trying to construct a 3-state PDA to recognise (I need to create a transition diagram for this question) ...
49 views

### Context-free grammar how to have unequal number of a's on either side of b

I have been trying to create a CFG for the set $\{w=a^iba^j \mid i \neq j\}$. To my understanding, there are essentially 2 scenarios, one where there are more $a$s on the left side of $b$, and one ...
26 views

### How to split a context-free language into three sub-languages?

I try to split the language $$L = \{a^ib^j \mid i \neq 2j, i \neq 3j\}$$ into three languages \begin{align} L_1 &= \{a^ib^j \mid i < 2j\} \\ L_2 &= \{a^ib^j \mid 2j < i < 3j\} \\ ...
37 views

### I want to design a context free grammar for the following [closed]

This below language $$L = \{ w \in \{a, b\}^n : \lvert w\rvert \text{ mod } 3 = 0 \}$$ where $n \geq0$.
105 views

### LL(k) language and not LL(k) grammar

I have nonambiguous and not LL(k) grammar which defines some language. How can I prove that I can't build some LL(k) grammar for this language? Grammar: S -> a b X c d | a X f X -> b X c | ε
17 views

### Formal definition for strong equivalence of grammars/parse trees

The Wikipedia article on equivalence of formal grammars defines weak and strong equivalence as follows: In formal language theory, weak equivalence of two grammars means they generate the same set ...
35 views

50 views

### Acyclic Manhattan turtle

There is a grammar that describes the walks of a turtle around Manhattan, such that the turtle always returns home. It is described in the book "Parsing Techniques" by Dick Grune and Ceriel J.H. ...