Questions tagged [formal-grammars]

Questions about formal grammars, generative descriptions of formal languages.

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

Making a simplest possible CFG to recognize the language L = {a^i b^j c^k | i + j ≥ 2k}

The language given is $L = \{a^i b^j c^k\mid i+j \ge 2k\}$ for which I need to construct a simplest possible Context Free Grammar. I tried understanding but I could only go as far as making sense of $...
0
votes
0answers
16 views

How to prove that this "priority" strategy (in ANTLR4) solves the "dangling-else" ambiguity?

As shown in this post @ stackoverflow, ANTLR4 seems able to resolve the "dangling-else" ambiguity @ wiki in the following "if-then-else" grammar by prioritizing the "...
2
votes
1answer
33 views

How does LALR(1) parser behave compared to LR(1) paser?

In Section 4.7.4 of the book "Compilers: Principles, Techniques, and Tools" (2nd Edition), it reads: "The revised parser (LALR(1)) behaves essentially like the original (LR(1)), .... ...
-1
votes
1answer
50 views

Proving language is not context-free with pumping lemma

I'm trying to prove that this language is not context free using pumping lemma. I am having difficulty as to where to even start on this. $$\{c^{2i} d^j b^{2j} d^k c^{3j} \mid i,j,k \ge 0\}$$
1
vote
0answers
53 views

Is there a complexity measure on regular grammars connected to the descriptional complexity of the DFAs?

This question is directed at DFAs/NFAs and regular languages and regular grammars. Define the "descriptional complexity" of a language as the size complexity of the family of DFAs that ...
0
votes
1answer
34 views

References to deterministic time complexity of language classes

It's fairly well known that $REG \in TIME(n)$. I would like to know similar inclusions for the language classes $DCFL$ and $CFL$. I have found a variety of claims for these classes on the internet. ...
0
votes
1answer
25 views

Grammar where the precedence of condition operators are asymmetric with regard to assignment operators

In Unix shell programming, there's the ideom: program1 && program2 && program3 where successful completion of ...
2
votes
1answer
34 views

What does $g \to \lambda$ mean in the L-System for the dragon curve?

I am playing with L-System using the wonderful tool jflap. Below is the L-System for the dragon curve in the "JFLAP book: JFLAP – An Interactive Formal ...
2
votes
1answer
30 views

Convert a dfa to rule for a asterisk case

Here is a simple but very common grammar rule case in EBNF format, the Statements is a none terminal symbol and Statement is ...
-1
votes
0answers
25 views

Say what language is generated by the context-free grammar

In each case below, say what language (a subset of {a, b}∗) is generated by the context-free grammar with the indicated productions. S→ aSa | bSb | aAb | bAa A → aAa | bAb | a | b | Λ I tried to solve ...
-1
votes
0answers
33 views

$Prove\; that\; L=a^i b^j c^k: i\le j\le k$ i s not context free language

Proof-: Assume L is CFL. Let p is pumping constant for L. w exists in L such that |w|$\ge p$ Let w=$a^p b^p c^p$ |w|$\ge$3p so everything is fine. Now let us see all decompositions of w such that-: vy$...
-1
votes
1answer
31 views

I can't visualize what happens when we pump v and y in pumping lemma for $a^n b^n c^n$

If you need some context-: https://www.andrew.cmu.edu/user/ko/pdfs/lecture-11.pdf around page 7. Case 1-: Say vxy contains ab So when I pump v and y, what will get pumped? And how the result would be. ...
1
vote
1answer
29 views

CFG for L={a^i b^j c^i; i,j > 0}

I worked a bit on this and got this-: S->ABC A->aA/a B->bB/b C->cC/c The obvious problem here is I am unable to count number of a's and c's which ...
-2
votes
0answers
52 views

Regular grammar for language that does not contain "abab"

I tried this : $V = \{S,A,B\}$ and $T = \{a,b\}$. $S \rightarrow aS | \epsilon | abaAS | BS$ $A \rightarrow a | aA$ $B \rightarrow bB | \epsilon$ Any thoughts/objections?
0
votes
0answers
13 views

Tips on making a grammar LL(1)?

So I currently am given the following grammar, and I have to make it LL(1). To do this, I need to remove ambiguities, eliminate left recursion, and left factor if necessary. But looking at this, it's ...
0
votes
1answer
19 views

What is the subset of CFGs called where each expansion must be the same?

I was wondering about a kind of grammar where we can expand rules of the form A -> X|Y|... with A being a nonterminal and <...
0
votes
1answer
23 views

LALR lookahead is wrong, why?

I am studying LALR(1) parser and I have this question: Consider the following Grammar S - > V = E E - > F | E+F F - > V | int | (E) V - > id Construct the LALR(1) parsing table for this ...
1
vote
2answers
42 views

PDA with multiple element access - $i$ - access PDA

We define an $i$ - access PDA as a PDA that can manipulate the top $i$ characters in the stack, where $i>0$. Given a transition function of the form $\delta(p,x,c,d) \to (q,c')$, where $d \le i, d &...
0
votes
1answer
23 views

Variant of Chomsky Normal Form for Languages with Strings of Length $\ge 2$

Given a context-free grammar $G$ for a language $L$, where $L$ contains strings of length greater than 2, show that there exists some context-free grammar $G'$ which generates $L$ such that every rule ...
0
votes
0answers
30 views

How to convert PDA to CFG and make a state diagram

I'm trying to understand this but I can't figure out how to proceed, I have an initial procedure but I don't know if it's right, could someone give me examples of how to do this? My attempt S→q0 Z q2 →...
1
vote
1answer
57 views

Stuck with shift-reduce conflicts on yacc on grammar to generate palindromic strings on {0,1}

I have written a yacc program for generating palindromic strings consisting of 0s and 1s. Here is the rules section of the yacc program below: ...
1
vote
1answer
85 views

Hierarchy of parser grammars vs Chomsky hierarchy of grammars and the comparsion of the language acceptance power of each parser grammar

While reading the text Modern Compiler Implementation in C by Andrew Appel I came across the hierarchy of grammar given below. The above diagram is very helpful in understanding the correlation among ...
0
votes
1answer
45 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
149 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
75 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
111 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
158 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
93 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
59 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
66 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
39 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
47 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
83 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
67 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
60 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
30 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
330 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
61 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
24 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
33 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
1answer
60 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
52 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
33 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
125 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
32 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 ...

1
2 3 4 5
23