Questions tagged [formal-grammars]
Questions about formal grammars, generative descriptions of formal languages.
1,251
questions
-2
votes
1
answer
37
views
Can you help with a contex-free grammar for the language 0^n 1^m 2^k where n+ 2k >= m? [duplicate]
Can you help with a contex-free grammar for the language 0^n 1^m 2^k where n + 2k >= m?
12
votes
2
answers
558
views
What is the closure of context-free languages under finite intersections?
Famously the intersection of context-free languages need not be context-free. On the other hand the intersection of context-sensitive languages is context-sensitive.
So this leads to the question: ...
- 121
0
votes
1
answer
23
views
How would you specify a grammar that can parse letters separated by single underscores?
In JavaScript, let's say, it is easy to build a string intermixed with single underscores by just joining the string parts.
...
- 2,163
1
vote
1
answer
80
views
Is $L = \{xw^3x^{rev}\mid x, w\in\{0, 1\}^*\}$ context-free?
The title pretty much explains the question, but still: Is the language
$$L = \{xw^3x^{rev}\mid x, w\in\{0, 1\}^*\}$$
context-free?
I think it isn't and would motivate that suspicion by the following ...
- 175
0
votes
1
answer
27
views
Does this grammar accept this words?
I made this grammar:
$S \rightarrow ASa$
$S \rightarrow c$
$A \rightarrow a|b$
And I want to check that it accepts words like $aacaa$, $abcaa$, $babcaaa$, I formed the grammar by thinking about the ...
0
votes
1
answer
105
views
Prove that grammar accepting arithmetic expressions is not regular
I created a grammar which accepts all arithmetic expressions consisting of $+,-,*,/, (, )$.
I created the following grammar:
$S \rightarrow M+-M$
$+-M \rightarrow +M+-M$
$+-M \rightarrow -M+-M$
$+-M \...
- 3
0
votes
0
answers
40
views
Grammar for all words $0^n1^m$ such that $n \ge m+2$
Given grammar
$$L(G) = \{ 0^n1^m | n \ge m + 2 \}$$
What is the grammar for this?
I know the grammar for the following language:
$$ L(A) = \{ 0^n1^m | n = m + 2 \} $$
We can divide any string in $L(A)$...
- 125
1
vote
1
answer
66
views
What is appearance checking in the context of formal grammars?
As I did not find any definition of the term "appearance checking" although it is widely used, I am eager to ask as what it can be defined.
Perfect would be an example using a context free ...
- 13
1
vote
2
answers
52
views
Is there a grammar for this language? $w^{m-1}aca^m$?
I have to form a free context grammar for this language $w^{m-1}aca^m$ where $w \in \{a,b\}$, so what I have been able to do is this:
$X \rightarrow SacA$
$S \rightarrow aS|bS$
$A \rightarrow aA$
But ...
- 21
0
votes
1
answer
166
views
How to demonstrate unambiguous CFG and CNF?
I have to show that if G is an unambiguous CFG, the transformed grammar G' in CNF is also unambiguous. But couldn't come up with something concrete. I could only visualize the case where the grammar G ...
1
vote
0
answers
44
views
Unambiguous formal grammars for a specific class of languages
Suppose that $w \in \{0; 1\}^*$ is a binary word. Let's denote the number of $0$-s in $w$ as $\#_0(w)$ and the number of $1$-s in $w$ as $\#_1(w)$.
Now suppose that $q \in \mathbb{Q}$ is a positive ...
- 131
0
votes
0
answers
1k
views
How LR parser works with grammar containing epsilon productions
In Dragon book for compiler design there is this example of SDT in Example 5.16
$L\rightarrow En$
$E\rightarrow \{ print (' +') ; \} \space E_1 + T$
$E\rightarrow T$
$T\rightarrow \{ print (' *' ) ; ...
- 281
-2
votes
1
answer
188
views
Finding the language generated by this grammar
I'm having problems with this. Can someone help me please.
Find the language generated by this grammar over the alphabet $\{0,1\}$:
$S\rightarrow BAB\mid CAB$
$BA \rightarrow BC$
$CA \rightarrow AAC$
...
- 3
1
vote
1
answer
47
views
Myhill-Nerode - Prove irregularity for $\{a^{n^3}\}$
I need to prove that the following language is not regular by showing there are infinite pairwise distinct equivalence classes:
$$
L = \{a^{n^3} \mid n \geq 1\} \subseteq \{a\}^*
$$
Looking at a ...
- 145
1
vote
0
answers
49
views
Checking correctness of grammar for $L = \{w \in \{a, b\}^* \text{ }| \text{ } w \text{ has } n_a(w) = 2n_b(w)\} $
I have written a CFG that supposedly generates $L$ below.
$$L = \{w \in \{a, b\}^* \text{ }| \text{ } w \text{ has } n_a(w) = 2n_b(w)\}$$
Where $n_a(w)$ is the number of $a$'s in $w$ and similarly for ...
- 258
0
votes
0
answers
34
views
Algorithmically find a formal grammar for a recursively enumerable formal language
The algorithmic problem is as follows.
The input is the source code of a program accepting an integer as input and outputting a finite binary sequence. This program defines a recursively enumerable ...
- 1
1
vote
2
answers
191
views
Are decidable set/languages EQUIVALENT to type 1 grammars (non-contracting)?
Suppose a Turing Machine (TM_G) that generates natural numbers following < or, equivalently, it generates words in lexicographical order.
Then, that language/set is decidable. Because it is trivial ...
- 135
4
votes
1
answer
162
views
Existence of a CFL $L$ such that $\sqrt{L}$ is not CFL
Does there exist a CFL L such that the language defined as $L' = \sqrt{L} = \{w | ww \in L\}$ is not CFL? I feel that there is no such $L$ but obviously, I am unable to prove it.
I am sorry but I have ...
- 271
1
vote
0
answers
22
views
How do bottom up parser evaluate things that need an inherited attribute?
I learned that Bottom up parsers use only synthesized attributes to evaluate semantics. Which makes sense considering that it would be very hard to evaluate an inherited attribute in bottom up ...
- 57
0
votes
1
answer
47
views
Context free grammar transformation to Normal Form
I found a task where you need to transform context free grammar to normal form.
I'm a High Shcool student at this moment. But my Brother learning this at the university. He don't have much time to ...
0
votes
1
answer
373
views
Grammar for $\{a^n b^n c^m d^m \mid n \geq 1, m \geq 0\}$
I'm trying to understand how the construction of simple grammars works.
In my textbook, there's the following example I am supposed to find a grammar for:
Let $L_1= \{a^n b^n c^m d^m \mid n \geq 1, m ...
- 145
4
votes
1
answer
934
views
Can a language be context free and not have a BNF grammar?
Leslie Lamport claims that TLA+ is too complex to be described in BNF.
Does that mean TLA+ is not a context free language?
What is the relationship between the set of context free languages and the ...
- 1,731
-1
votes
1
answer
88
views
Grammar for $L=\{a^{i+1}b^{i}c^{2j}d^je^{2j}|i,j>0\}$
I'm supposed to write grammar for this language: $$L=\{a^{i+1}b^{i}c^{2j}d^je^{2j}\mid i,j>0\}$$
This is what I have so far:
$$\begin{align}
S &\to aXbY \; \\
X &\to aXb \;|\; a \\
Y &\...
- 11
0
votes
2
answers
255
views
Proving that a language defined by a regular expression is equivalent to a right linear grammar
After thinking for a bit, I am not able to prove a double inclusion proof for the following problem. It seems very interesting to me.
Consider the regular expression $r= ((1(00)^∗1 + 0)1)^∗$ and the ...
- 11
1
vote
2
answers
162
views
Proving that $X\to aX|Y$, $Y \to Yab|b$ is unambiguous
Prove that the following grammar is unambiguous:
$$X \to aX | Y$$
$$Y \to Yab | b$$
I know that I must prove that the strings produced by this grammar have only one parse tree, but how can I do this?...
- 75
0
votes
1
answer
300
views
BNF syntax for a recursive function?
I'm to write a syntax that will allow for a recursive function, i.e.
f(x) = if x == 0 then x else f(x+1)
Here's one attempt at creating the grammar:
But I don't ...
- 155
3
votes
2
answers
686
views
Why does the Java grammar have a StatementExpression that resolves to just Expression? Why have this and other redundant rules in the grammar?
I'm looking at the following grammar rules for the Java language described on the Oracle docs:
...
- 133
0
votes
1
answer
395
views
CFG for $L=\{a^m b^n c^k | m,n,k > 0, k\neq m+n\}$
I started learning CFG and I'm trying to find CFG for this language, but I have no idea where to start and I can't seem to find this one online anywhere. It would be great help, if someone could show ...
- 11
1
vote
0
answers
33
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 $+$, $*...
- 11
1
vote
1
answer
682
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 ...
- 1,112
1
vote
3
answers
3k
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)^*$:
\...
- 11
2
votes
2
answers
135
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 \...
- 121
2
votes
2
answers
213
views
Arguing that $L= \{a^n | n\geq 0\} \cup \{a^nb^n| n\geq 0\}$ is not $LL(k)$ for any $k$
Consider the language $L= \{a^n \mid n\geq 0\} \cup \{a^nb^n\mid n\geq 0\}$ and the following statements.
$\quad\quad\text{I. }L$ is deterministic context-free.
$\quad\quad\text{II. }L$ is context-...
- 1,112
0
votes
1
answer
56
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 ...
- 123
1
vote
1
answer
36
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
1
answer
31
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$ ...
- 29
1
vote
1
answer
83
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 ...
- 11
0
votes
1
answer
148
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
1
vote
1
answer
128
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$, ...
- 15
0
votes
1
answer
42
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 ...
- 119
0
votes
0
answers
33
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?
- 1
0
votes
1
answer
190
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 ...
- 185
1
vote
2
answers
226
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 ...
- 11
0
votes
1
answer
160
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: ...
- 21
0
votes
1
answer
36
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-...
- 175
2
votes
1
answer
241
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\}$?
- 125
0
votes
0
answers
21
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
1
vote
0
answers
56
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 ...
- 175
0
votes
1
answer
30
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?
- 139
2
votes
1
answer
51
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 ...
- 35