Questions tagged [formal-grammars]
Questions about formal grammars, generative descriptions of formal languages.
942
questions
0
votes
1answer
15 views
Is this grammar LL(1) grammar?
Is this grammar LL(1)? Would it be a problem that S can be both E/S and E?
S -> E / S
S -> E
E -> letter
E -> ‘ S ’
Can it derive ‘a / e / ‘g / s’ ’...
0
votes
0answers
55 views
I´m having problems with this Context Free Grammar
I am not able to convert the following language to a Context Free Grammar. The major problem is how to pump both "sides" of the word to obtain same number of 0s and 1s, but, without creating a series ...
0
votes
1answer
19 views
Textbook for understanding formal grammars
I am looking to understand the Chomsky Hierarchy. I've read some textbooks that touch on formal grammars (textbooks on computability, which relate automata to specific sets of formal grammars, notably ...
0
votes
1answer
58 views
Why LL(1) grammar generate all regular languages?
I came across following:
Every regular language has right linear grammar and this is LL(1). Thus, LL(1) grammar generates all regular languages.
I tried to get that.
Definition: Right linear ...
0
votes
1answer
28 views
Adding constraints in grammar for Grammatical Evolution
I'm trying to use Grammatical Evolution for creating trading strategies. Each sentence in the grammar when evaluated gives a weight matrix of size n x p . (n is the length of backtesting period and p ...
0
votes
1answer
13 views
Ambiguous Grammar demostration exercise
Hi im stuck on an exercise of ambiguous grammar. I need an example that shows that this grammar is ambiguous. The grammar is defined as follows:
$$S \rightarrow aT | bR$$
$$R \rightarrow a | aS | bRR$...
1
vote
1answer
30 views
How to write grammar production rules to describe recursive structures?
I'm trying to describe a data structure by production rules. The structure is recursive; say a list of type $A$ made of elements of type $A$ or $B$.
Writing the grammar, I build this:
$(S \...
2
votes
1answer
33 views
How does $LL(n)$ languages compare with $LR(0)$, for $n>0$?
In the context of languages (not grammars), I know following:
$LL(0) \subset LL(1) \subset LL(2) \subset \cdots \subset LL(k)$
$LR(0) \subset SLR(1) = LALR(1) = LR(1) = SLR(k) = LALR(k) = LR(k)...
2
votes
2answers
88 views
Grammar with fewest variables
I am looking over a past exam for a theory of computation class I am taking, and unfortunately no solutions are provided. I am stuck on this question, and would greatly appreciate any help or hints.
...
1
vote
1answer
38 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
51 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
48 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
176 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 \...
2
votes
1answer
82 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
146 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
vote
2answers
27 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
42 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
151 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
30 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
39 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
78 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
45 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
29 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
56 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
54 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
20 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
22 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
259 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
101 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
73 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
136 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
90 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
60 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
43 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
44 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
40 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
20 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
113 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
54 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
27 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
39 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
113 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 | ε
