Questions tagged [formal-grammars]

Questions about formal grammars, generative descriptions of formal languages.

Filter by
Sorted by
Tagged with
0
votes
1answer
17 views

Find a Context-Free Grammar for $L:=\{a^nb^mc^{n+m}\mid n,m\in\mathbb{N}\}$

I want to find a Context-Free Grammar for $L:=\{a^nb^mc^{n+m}\mid n,m\in\mathbb{N}\}$ I've tried the following: $G=(V,\Sigma,R,S)$ with $\Sigma=\{a,b,c,\lambda\}$, $V=\{S,B\}$, $S=S$ and $$R=\{S\to \...
0
votes
1answer
40 views

Convert ambiguous grammar to unambiguous and SLR(1)

I have the following ambiguous operator grammar: E->E+E*E | E-E*E E->E+E | E-E | E+E | E*E | E/E E->(E) | x I must convert it to an unambiguous one ...
0
votes
0answers
27 views

Deciding whether CFG generates the empty word

Give an algorithm to decide the following problem: given a CFG $G$, does $G\Rightarrow^\star \epsilon$? That is, given a grammar can it generate the empty word? How can I make sure my algorithm is ...
0
votes
0answers
34 views

Grammar for language L on {a, b} where L = {w|na(w)mod 3 = 0} [duplicate]

I am able to form the regular expression but I am not confident with the grammar. I have tried the following: S-->aaaS|bS|b|lambda Regular expression is given by: ...
2
votes
1answer
114 views

How to simplify context free grammars?

How to simplify this context-free grammar? $$ S \to ACD \\ A \to a \\ B \to \varepsilon \\ C \to ED \mid \varepsilon \\ D \to BC \mid b \\E \to b $$ Can the simplification result in this CFG? $$ S \...
-1
votes
0answers
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
2
votes
1answer
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{...
3
votes
2answers
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.
-1
votes
0answers
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?
1
vote
2answers
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.
0
votes
1answer
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 ...
3
votes
0answers
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 ...
1
vote
1answer
24 views

What does the term “top-most” mean in the context of formal grammars?

I was learning about disambiguating grammars. In particular I was learning about enforcing right associativity on the sum language here: $$ \mathit{Sum} ::= 0 \mid 1 \mid \mathit{Sum} + \mathit{Sum} \...
0
votes
0answers
27 views

Converting from cfg to cnf (Chomsky normal form)

I am trying to convert this grammar from context free grammar with kleene star productions into the Chomsky normal form equivalent. I am having a hard time trying to understand how to do this, I need ...
1
vote
1answer
35 views

Making a CFG for a^i b^j c^k such that i+k < 3j

I have the language $L = \{ a^ib^jc^k \mid i + k < 3j \}$, however I am struggling to convert it to a CFG. I have thought about solving this for a long time but but this still hasn't gotten me ...
-2
votes
2answers
77 views

Why Rice theorem work for decidability?

Rice's theorem states: Every nontrivial property of recursively enumerable language is undecidable. I came across following problems, which Ullman's books say both are undecidable: Turing ...
1
vote
1answer
44 views

What is the computational power of Parsing Expression Grammars?

Parsing Expression Grammars were introduced by Bryan Ford in Parsing Expression Grammars: A Recognition Based Syntactic Foundation.. Wikipedia says that it is an open problem to provide a Context Free ...
0
votes
0answers
28 views

Are these two things parsing a sentence and solving a problem in a turing machine equivalent?

I'm an undergrad currently studying Advanced Topics in Algorithms, Compiler Techniques, and Natural Language Processing. I'm wondering whether these two things are equivalent. Given a sentence and a ...
1
vote
0answers
51 views

Prove that grammar $S \to aSc | \epsilon | bBc$ ,$B \to bBc | \epsilon$ generates language $\{a^ib^jc^{i+j} | i,j \ge 0 \}$

Prove that grammar $G$ with productions: $S \to aSc|\epsilon | bBc$ $B\to bBc | \epsilon$ Generates language $ L = \{a^ib^jc^{(i+j)}$ | $i,j \ge 0 \} $ Step 1. Prove $L(G) \subseteq L$ . ...
1
vote
1answer
19 views

Variable derives itself

In Sipser's Introduction to the theory of computation (3rd edition), I found the following claim. Consider the grammar: $$ \begin{align*} &R \to XRX \mid S \\ &S \to aTb \mid bTa \\ &T \...
0
votes
1answer
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 ...
0
votes
0answers
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.
0
votes
0answers
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 ...
6
votes
1answer
253 views

Are these special (one production) Context-Free Grammars always unambiguous?

Consider the following (Context-Free) Grammars with only one production rule (not including the epsilon production): $S \rightarrow aSb\;|\;\epsilon$ $S \rightarrow aSbS\;|\;\epsilon$ $S \rightarrow ...
2
votes
2answers
99 views

Grammar and Real-numbers

I am curious about following question. I've read other threads but the problem is slightly different: Is the set of real numbers a language? So my question is: If I have a grammar, as defined in ...
2
votes
1answer
41 views

How do I call a system like a grammar, but where a rule has to be applied to all matches at once?

For example, given rules $\{ a \to x, a \to y \}$ and input $aa$ , I am usually allowed to derive strings $\{ xx, xy, yx, yy \}$. I would like to restrict this to only performing "consistent" rewrites,...
2
votes
1answer
70 views

Context-free grammar for $\{a^x b^y : x \neq y\}$

I am trying to create a context free grammar in Extended Backus–Naur form, which starts with a non-empty sequence of a's and is followed by a non-empty sequence of <...
5
votes
3answers
135 views

How do I calculate the Nth result of a context-free grammar?

Given a context-free grammar and a maximum depth, how do I directly compute the Nth sentence without calculating or caching intermediary sentences? Take as an example the following grammar: (from ...
2
votes
1answer
83 views

Are Context-Free Grammars with only one Production Rule always Unambiguous?

Consider the following (Context-Free) Grammars with only one production rule (not including the epsilon production): $S \rightarrow aSb\;|\;\epsilon$ $\require{cancel} \cancel{S \rightarrow aSSb\;|\;\...
0
votes
1answer
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: ...
1
vote
1answer
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: ...
1
vote
1answer
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 ...
2
votes
1answer
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?
1
vote
1answer
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+...
0
votes
1answer
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 (...
0
votes
0answers
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 ...
0
votes
1answer
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" ...
-1
votes
1answer
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, ...
1
vote
0answers
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) ...
1
vote
1answer
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 ...
3
votes
1answer
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\} \\ ...
1
vote
1answer
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$.
2
votes
1answer
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 | ε
0
votes
0answers
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 ...
0
votes
1answer
35 views

Are you allowed to use index variables in grammars?

If we say that the grammar for the language $L = \{ww \mid w \in \{a,b\}^*\}$, is: $\begin{align} S &\rightarrow A_1A_2S \mid B_1B_2S \mid Z_2\\ A_2A_1 &\rightarrow A_1A_2\\ A_2B_1 &\...
1
vote
0answers
32 views

Ambiguos Grammar detection algorithm

I tried to solve if a grammar is ambiguous or not. I know that I have to find a word that can be generate by two different leftmost derivations. Is there any algorithm to find a word that, if the ...
2
votes
1answer
33 views

What is the density of a regular language $L$ over an alphabet $\Sigma$ in $\Sigma^n$?

In other words, what is the likelihood that a recognizer of a given regular language will accept a random string of length $n$?   If there is only a single non-terminal $A$, then there are only ...
4
votes
0answers
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. ...
0
votes
0answers
30 views

Conversion of left-recursive context-free grammars to strongly equivalent ones without left-recursion

It is a well-known problem that many top-down parsers have problems parsing a context-free grammar with left recursive rules. There exist algorithms to convert grammars with direct or indirect left-...
0
votes
0answers
55 views

Is Python's Grammar in a known Category between CFG and CSG?

I have a high level understanding of formal languages and grammars, and I'm familiar with the four major types of grammars in Chomsky hierarchy. I was interested in knowing the classification of ...