Questions tagged [formal-grammars]
Questions about formal grammars, generative descriptions of formal languages.
1,093
questions
1
vote
0answers
11 views
What to do with operators with the same precedence in an unambiguous grammar?
I'm trying to create an unambiguous grammar for a calculator that uses $+$, $-$, $*$, $/$ and $()$.
From watching videos and reading articles online, I understand how to create the grammar with $+$, $*...
1
vote
1answer
33 views
Difficulty in understanding the proof of “Every context-sensitive language L is recursive” as given in the Peter Linz text
I was going through the automata text by Peter Linz. There I came across the proof the theorem below. I could not quite get the portion of the proof in bolds.
Every context-sensitive language L is ...
0
votes
0answers
11 views
Difficultly in understanding the construction corresponding how any Turing machine can be mimicked by an unrestricted grammar
I was going through the automata text by Peter Linz where I came across the construction below.
To show the converse, we describe how any Turing machine can be mimicked by an unrestricted grammar. We ...
0
votes
0answers
38 views
Eliminating ambiguity in $A \to AA \mid (A) \mid a$
I'm trying to solve this complier design problem related to ambiguity in CFG the given grammar is
\begin{align}
&A → AA \\
&A → (A) \\
&A → a
\end{align}
I was able to find that this ...
1
vote
2answers
29 views
Converting a regular expression to a context-free grammar
Does this conversion look right? I am learning conversion from RE to CFG.
RE:
$$(a \cup b)^* \cup ab(a \cup b)^*$$
CFG:
Terminals:
$$ S_1 \to a \\ S_2 \to b $$
This is for the first $(a + b)^*$:
\...
1
vote
0answers
26 views
Generating a recursive descent parser for grammar having Kleene star
From what I have been taught, I cannot use left-recursive, nondeterministic, or ambiguous grammars in recursive descent parsers. So, here is the grammar:
\begin{align}
&E \to E+T \mid T \\
&T \...
3
votes
0answers
37 views
Arguing that $L= \{a^n | n\geq 0\} \cup \{a^nb^n| n\geq 0\}$ is not $LL(k)$ for any $k$
$\text{Consider the language $L= \{a^n | n\geq 0\} \cup \{a^nb^n| n\geq 0\}$ }$
$\text{and the following statements.}$
$\quad\quad\text{I. $L$ is deterministic context-free.}$
$\quad\quad\text{II. $L$...
1
vote
2answers
40 views
Language of regular grammar
What is the regular grammar of the language: $$L=\left\{a^nb^nc^md^m\left|n,m\ge 1\right|\right\}\:above\:\Sigma =\left\{a,\:b,\:c,\:d\right\}$$
My attempt: $$S\rightarrow aAbcBd|aXd$$ $$A\rightarrow ...
1
vote
1answer
28 views
Grammar for all words other than $wq,qw$
I want to generate a grammar that can't generate the words $qw$ and $wq$ but can generate the word $qwwq$. In other words, $L(G)=\{m ∈ \{q,w\}^* \mid m \neq wq,qw \}$.
My grammar:
\begin{align}
&S ...
0
votes
1answer
22 views
Words which, cyclically shifted twice, equal their reverse
Let the alphabet be $Σ = \{0, 1\}$. For any string $w ∈ Σ^*$ of length at least 2, define the
operation $C_2(w)$ to be a cyclic shift of size 2 on $w$. That is, if $w = w_1w_2 \cdots w_n$ with $n ≥ 2$ ...
1
vote
1answer
59 views
Construct a grammar for $\{a^n(bc)^m : m,n \ge 1, m < n/2\}$
I'm new to writing languages in context-free or regular grammar, so I'm struggling how to do this one. It is a bit more complicated that simpler ones I've practiced doing. The problem is to construct ...
0
votes
1answer
27 views
How do I represent this regular expression in regular grammar?
Question: Is the regular expression and regular grammar equivalent?
I've look on some examples of regular grammar however I don't think I fully understand how to convert regular expression to its ...
1
vote
1answer
105 views
Constructing a context-free grammar
I want to design a context-free grammar that generates words that either both start and end with $c$, or contain the same amount of $a$-s and $b$-s. Here is what I have. The nonterminals are $S,X,Y$, ...
0
votes
1answer
29 views
Regular set of the “does not contain” kind
Given a language $L$ and a set of strings $\Sigma^* = \{0, 1\}^*$, how can I find a regular set that expresses
$L = \{ w \in \Sigma^* \mid w$ ends with $00$ and does not contain $11\}$?
Well, the part ...
0
votes
0answers
23 views
How to change a grammar so that it can be unambiguous?
The original grammar is
$$ S \to SaS \mid SbS \mid ScS \mid d $$
My answer is
$$ S \to daS \mid dbS \mid dcS \mid d $$
Is that correct?
0
votes
0answers
16 views
L= ${ a^mb^nc^pd^q: m+n<>p+q }$ context free? [duplicate]
I cant find the grammar to prove it is context free but. I also tried a PDA but couldnt make it.
Can someone suggest a grammar for this?
0
votes
1answer
49 views
Which of the following words is in the language of the grammar G?
This is taken from a practice quiz by my university.
I ruled out that aabbbaab is not part of the grammar:
S → aSb → aaSbb... This shows that I can't make this word because it would have to have ...
0
votes
0answers
16 views
Why can't I evaluate this L-Attributed SDD with a pre-order traversal?
My powerpoints for a compiler class says "an L-Attributed SDD can be evaluated with a pre-order (root, left, right) traversal", and to be L-Attributed the nodes need to have either ...
1
vote
2answers
33 views
How to evaluate a Kleene's Closure through CFG and attribute grammars
For a CFG with the production rules that can represent a regular expression. How can one calculate all the set of strings that regular expression would produce.
For T = {a, b,*,(,)}
and an arbitrary ...
0
votes
1answer
45 views
How can I make the following grammar unambiguous
Given the below ambiguous grammar how can I make it inambiguous and how can I prove the new modified unambiguous grammar is unambiguous? S -> S + S | S − S | S ∗ S | S / S | (S) | x | y
My attempt: ...
0
votes
1answer
26 views
Formal Grammar: derivation form posted on Wiki?
Wiki describes the binary relation $\underset{\mbox{G}}{\implies}$ as "G derives in one step". I have a question on the condition when there are multiple productions for a single non-...
1
vote
1answer
49 views
Is it possible to make a grammar LL($1$) which recognizes palindroms?
Is it possible to make an algebraic grammar LL($1$) which recognizes palindroms for an alphabet $\{a,b\}$?
0
votes
0answers
18 views
generating strings from this formal grammar [duplicate]
Hey guys I am having trouble generating strings from this language, I haven't seen a grammar that looks like this and can't figure how to generate strings from this grammar, is this Context Sensitive ...
1
vote
0answers
52 views
A Formal Grammar: defining English counting numbers?
I would like to define a grammar that produces and recognizes the counting numbers of the English language. I created the production rules below based on the assumption this is context-free, but I am ...
0
votes
1answer
16 views
Compilers: How to see “the number of grammars where there exists a string that has at least two different left-most derivations”?
Could someone tell why "G1 and G3 are ambiguous" and how to see whether a string has at least two different left-most derivations in general?
2
votes
1answer
44 views
Proof that $L = \{a, b\}^* - \{(a^n b^n)^m \mid n, m \ge 1\}$ is a CFL
I want to prove that $L = \{a, b\}^* - \{(a^n b^n)^m \mid n, m \ge 1\}$ is a Context Free Language.
so far, I tried to find a Context Free Grammar for $L$ or to use properties of Context Free ...
0
votes
0answers
20 views
I am trying to design an LL(1) Parser that accepts T = {a, b *, +, ?, E, U, (, ) }
I am trying to design an LL(1) Parser that accepts regular notation where 'E' represents epsilon, and 'U' represents "or" like ' | '.
So far I made one that accepts T = { a, b, *, +, (, ), E}...
0
votes
1answer
36 views
Removing left recursion with terminals only
I have a grammar:
$G → id > id$
$| id < id$
$| G and id$
Does anybody know how I can do left recursive elimination on this one, when it doesn't have any extra non terminals?
1
vote
0answers
17 views
Compile XPath Abbreviated Query to Unabbreviated version
The Xpath 3.1 presented by W3C includes the full grammar of the language with both abbreviated and unabbreviated syntax.
I am interested in references (if any) for any formal work done to compile/...
3
votes
2answers
66 views
Context free grammar for $L = \{w \text{ | }w \in \{a,b\}^*, |w|_a=|w|_b-1\}$
I'm trying to find a grammar for $L = \{w \text{ | }w \in \{a,b\}^*, |w|_a=|w|_b-1\}$, which is proving to be tricky.
I know that $L_2 = \{w \text{ | }w \in \{a,b\}^*, |w|_a=|w|_b\}$ has the following ...
0
votes
1answer
42 views
Computing FOLLOW sets of left recursive grammar
Left recursive ambiguous expression Grammar:
$E \rightarrow E+E \mid E*E \mid (E) \mid \mathbf i\mathbf d$
I tried computing FIRST and FOLLOW sets of both left recursive grammar and after ...
1
vote
1answer
36 views
Is there a formal language of Combinatory Logic's expressions?
The Combinatory Logic uses expressions of the form (x y) called "applications" (here, we have an "application of x to y"). Thus, the language of CL is a set of "parenthetic ...
1
vote
1answer
76 views
Derivation from grammar
Given the grammar $G=(\{S, L_x, R_x, W_x\}, \{a,b\}, P, S)$ derive the words $abaaba$ and $aabbaabb$.
$$
P=\left\{
\begin{align}S\phantom{{}_x R_y} &\to \epsilon \mid L_x R_x,\\
L_x \...
1
vote
1answer
38 views
Finding a grammar for $L=\{a^nb^mc^rd^s| n+m<r+s\}$
I am trying to find a grammar for $L=\{a^nb^mc^rd^s| n+m<r+s\}$, which has the hint of it having "some similarity" to $L=\{a^ib^j|i<j\}$
This last one is quite easy to get ($S\to aSb | ...
2
votes
4answers
79 views
If $L$ is regular then $L^{|2|}=\{w_1w_2 \mid w_1,w_2\in L, |w_1|=|w_2|\}$ is context-free
I have found a problem about proving whether $L^{|2|}=\{w_1w_2 \mid w_1,w_2\in L, |w_1|=|w_2|\}$ is context-free or not, knowing that $L$ is regular
So far I know that:
There are examples where $L$ ...
1
vote
2answers
62 views
Finding a grammar for $L = \{ 0^x1^y0^z1^w | x+w=y+z\}$
I have found an exercise where it tasks to provide a grammar and a pushdown automata for
$L = \{ 0^x1^y0^z1^w | x+w=y+z\}$
While finding a pushdown automata for it is quite easy (four states and two ...
1
vote
2answers
186 views
Trying to remove ϵ rules from a formal grammar resulted in L(G) ≠ L(G')
I am trying to remove ϵ rules from the following grammar (after applying the remove redundant symbols algorithm): $G = (\{S,A,B,C\},\{0,1\},P,S)$, where the productions are
\begin{align}
&S \to AB ...
3
votes
1answer
50 views
Is there a method to generate the complement of a context-free grammar?
Given the languages $L_0 = {w \in \{0,1\}^*}$ such that $w$ is a palindrome and $L_1 = {w \in \{0,1\}^*}$ such that $w$ is not a palindrome, meaning $L_1$ is the complement of $L_0$, we want to find ...
0
votes
1answer
25 views
Is the complement of the language generated by $S \to aSbS|\epsilon$ context-free?
How is it possible to prove whether the language $\{a, b\}^{∗} \setminus \{S → ε, S → aSbS\}$ is context free?
4
votes
1answer
242 views
Context-free grammar for all words not of the form w#w
I was asked to define a CFG for the complement of $\{w\#w \mid w \in \{0,1\}^*\}$ and I'm struggling to define it. I think it is quite similar to defining a CFG for the complement of $\{ww \mid w \in \...
1
vote
1answer
30 views
Trying to find two CFGs for the following languages
I'm trying to get CFGs for these two languages which still remain unsolved in my practice problems sheet:
$L = \{ a^kb^ra^m | m=k+r\}$
$L = \{ a^nb^m | 1\leq n\leq 2m\}$
With the first one, I thought ...
0
votes
1answer
27 views
How can Chomsky hierarchy be applied to languages with alternated letters?
I have the following grammar, which I know it is regular because it can be represented by a finite state automata:
\begin{array}{l}
\mathrm{S} \rightarrow \mathrm{X} \mid \mathrm{Y} \\
\mathrm{X} \...
0
votes
0answers
22 views
Building Context sensitive grammars?
I just discovered Context-sensitive grammars.
The problem is most of the examples are weird non-interesting toy languages !
Second the descriptions are math oriented, rather than programmer oriented.
...
0
votes
0answers
26 views
Parsing a context free grammar, Backus Naur question
Does anyone know how BNF rules expecting the empty string ($\epsilon$ or the "") behave during creation of a parse tree using grammar from a string of ...
1
vote
1answer
660 views
What does it mean for a grammar to be LR(0)?
I am unsure what it means for a grammar to be $X$. More specifically, what it means for a grammar to be LR(0).
For part of an assignment I had to form the DFA for a grammar, which I had no issues with....
2
votes
1answer
69 views
How can I show that this language is context sensitive?
I have this language $L=\{a^nb^nc^n,n\geq0\}$, I know this language is not context free, but I don't know how to show that it is context sensitive, do I have to use a PDA?
0
votes
1answer
38 views
Formal proof of language accepted by a specific CFG
Let $G=(V,\Sigma,R,S)$ be the grammar given by the following rules:
\begin{align}
&S \to aS \mid B \\
&B \to abBc \mid \epsilon
\end{align}
Please provide a formal proof for the following ...
1
vote
1answer
64 views
How do you create a sentential form in a given grammar?
I am given the following grammar:
$$S ::= aBS| abT |a$$ $$T::= d | dT$$$$B ::= da | ϵ | S$$
I need to decide whether $aBaabda$ can be produced in the given grammar.
I am unsure how the grammar can ...
0
votes
0answers
14 views
Having trouble understanding how to prove a language context free? [duplicate]
I've been studying the theory of automata. I came across this problem in the book and unable to understand how to solve this. I've solved some examples using the Pumping lemma but this one uses ...
1
vote
1answer
72 views
How can we generate a grammar for $\{a^n b^n c^n d^n; n > 0\}$ if it is NOT context free?
This page on Wiki states that $\{a^nb^nc^nd^n \ | \ n > 0\}$ can not be generated by a CFG. This does not make sense to me as $\{$S $\to$ ABCD, A $\to$ aA | a, B $\to$ bB | b, C $\to$ cC | c, D $\...
