Questions tagged [formal-grammars]

Questions about formal grammars, generative descriptions of formal languages.

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

Formal proof of existence of equivalent parse tree for each derivation

Where I can find formal proof of there exists an equivalent parse tree for each derivation? There is a lot of informal proof of equivalency on the internet but I need formal proof to reference it in a ...
0
votes
1answer
42 views

Can a grammar that has only one leftmost derivation tree for every sentence, have more than one rightmost derivation tree for some sentence?

I'm currently studying the book Engineering a Compiler by Keith Cooper, and in chapter 3, there is the following definition: A grammar G is ambiguous if some sentence in L(G) has more than one ...
1
vote
1answer
60 views

Easy-to-prove example of non-contextual language

When studying Chomsky's hierarchy of languages (starting from type 3), I find enlightening to encounter some language that can't belong to the current type but which very obviously belong to the next ...
2
votes
1answer
82 views

Dragon book 4.4.5 exercise?

...
1
vote
0answers
29 views

Algorithm for transforming all left-recursive rules in a grammar into direct left-recursive

I'm probably missing a lot of terminology here, so I'll try to rather be too clear than too vague. I have a Context-Free grammar as an input, that might contain direct or indirect left-recursion ...
3
votes
1answer
156 views

Is the emptiness problem for PEGs decidable?

The emptiness problem for Context Free Grammars is decidable. Does the same hold for Parsing Expression Grammars (PEGs)? That is, is it decidable given a PEG $G$ to find whether $L(G) = \emptyset$ or ...
3
votes
1answer
65 views

Context free grammar for strings with more $a$'s than $b$'s

I would like to prove that the grammar $G$ with the rules $$ S \to SS \mid aSb \mid bSa \mid a \mid \varepsilon $$ generates the language $L = \{w \mid \text{$w$ has at least as many $a$'s as $b$'s}\}$...
0
votes
2answers
54 views

How to define a formal language for describing procedural activities

I do not have a formal computer science background here so I am looking for pointers. How would you advice I go about describing a formal way to describe procedures like cooking recipes, manufacturing ...
1
vote
1answer
54 views

What is the formal definition of precedence and associativity in programming language?

The concept of precedence and associativity seems straightforward. The operator precedence is a collection of rules that reflect conventions about which procedures to perform first in order to ...
1
vote
0answers
26 views

Has anyone seen the following string classifier discussed?

The closes related question I have found for this is Find string patterns preferably in regex for string streams, but it has no answer and is also a little less constrained as my idea. Given a set of ...
2
votes
1answer
29 views

Left recursive grammar to right recursive grammar

I am studying conversion from left recursive grammar to right recursive grammar. The given grammar is $$E \to E + T \mid T $$ It's equivalent right recursive grammar will be $$\begin{align}E &\to ...
1
vote
1answer
40 views

Proof of an interesting language being non-context free

Let $\Sigma = \{a, b, c\}$ and $L = \{wa^{1 + k + 2n}b^nw^{rev}\mid n, k \in \mathbb{N}_0, w \in \Sigma^*\}$. It is clear that $L$ is context free, but the question is the following: Let $L'$ be the ...
0
votes
1answer
54 views

What's the Context-Free grammar of this language : $L= \{a^n b^m c^p d^q |m+n=p+q, n,m,p,q \geq0 \}$ [duplicate]

I was trying to find the context-free grammar of `$L= \{a^n b^m c^p d^q |m+n=p+q, n,m,p,q \geq0 \}$ but I'm stuck. This is what I did so far: $$ S \to X S Y | \lambda$$ $$X \to a|b$$ $$Y \to c|d $$ ...
-3
votes
1answer
51 views

How can I convert from DFA in to regular grammar?

I have following information. 0 1 -> *q0 q0 q1 q1 q1 q2 q2 q2 q0 I have to convert this in to a regular grammar. I wrote this: ...
1
vote
2answers
57 views

If $p(n) := \sum_{i=0}^ka_in^i$ where $a_i\in\mathbb{N}, a_k \ne 0$ AND $k \ge 2$, is $L = \{0^n1^{p(n)} \mid n\in\mathbb{N}\}$ context-free?

I have the really strong feeling it is indeed NOT context-free, since the language $1^{n^k}$ for $k\ge 2$ is not context free (proven by the pumping lemma) and, in a sense, "the order of ...
-2
votes
1answer
29 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?
9
votes
2answers
322 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: ...
0
votes
1answer
20 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. ...
1
vote
1answer
58 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 ...
0
votes
1answer
25 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
1answer
22 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 \...
0
votes
0answers
32 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)$...
1
vote
2answers
58 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 ...
1
vote
2answers
49 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 ...
0
votes
1answer
31 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
0answers
32 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 ...
0
votes
0answers
64 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 (' *' ) ; ...
0
votes
0answers
27 views

Prove $L =\{0^{2^n}\mid n \geqslant 0\}$ is not context free [duplicate]

Here $0^j$ means $0$ repeated $j$ times e.g. $0^2$ is $00$. So to prove this I was asked to use the pumping lemma. So let $m$ be the pumping length and assume $L$ is a CFL by contradiction. We can ...
-2
votes
1answer
49 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$ ...
1
vote
1answer
33 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 ...
1
vote
0answers
45 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 ...
0
votes
0answers
20 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
vote
2answers
65 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 ...
3
votes
1answer
66 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 ...
1
vote
0answers
12 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 ...
0
votes
1answer
23 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
1answer
42 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 ...
4
votes
1answer
753 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
votes
1answer
73 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 &\...
0
votes
2answers
46 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 ...
1
vote
2answers
57 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?...
0
votes
1answer
22 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 ...
3
votes
2answers
672 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: ...
-1
votes
1answer
47 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 ...
1
vote
0answers
14 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
47 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
40 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
55 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
34 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 \...

1
2 3 4 5
23