Questions tagged [formal-grammars]
Questions about formal grammars, generative descriptions of formal languages.
940
questions
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 ...
