Questions tagged [formal-grammars]

Questions about formal grammars, generative descriptions of formal languages.

Filter by
Sorted by
Tagged with
4
votes
3answers
255 views

Designing a CFG that produces as many c's as the difference of numbers of a's and b's

The question is to design a CFG for the language of words that have as many c's as the difference of numbers of a's and b's, that is $\qquad\displaystyle L = \{(a^l)(b^m)(c^n) \mid l, m \in \mathbb{N}...
4
votes
1answer
570 views

Is this phrase structure grammar from my textbook correct?

I just started reading "Parsing Techniques, A Practical Guide", Second Edition, by Dick Grune and Ceriel J.H. Jacobs. On page 12, the authors start describing a set of rules that can be used to ...
4
votes
1answer
535 views

Proof of equivalence of parse-trees and derivations

Intuitively, every derivation in a context-free grammar corresponds to a parse-tree and vise versa. Is this intuition correct? If so how can I formalize and prove such a thing?
4
votes
1answer
42 views

Language containing all unambiguous grammars

Suppose $L$ is the language of the unambiguous grammars. That is, a sentence $w\in{}L$ if it is a string that describes an unambiguous context-free grammar. Considering that deciding whether a ...
4
votes
1answer
71 views

Is there a recommended process for designing CSGs (other than intuition)?

I understand the differences between Regular, Context-Free, and Context-Sensitive languages. Designing a Regular Grammar can be easier if you have a DFA. Designing a CFG isn't too hard for the ...
4
votes
1answer
855 views

Bottom-Up Parser With Leftmost Derivation

I'm reading the book Parsing Techniques by Dick Grune et al. and in section 3.1.3 "Linearization of the Parse Tree" they introduce the notion of linearization: [...] a parser can produce a list of ...
4
votes
1answer
152 views

An intuitive explanation for LR grammars?

With LL grammars, there seems to be a very intuitive explanation, in terms of first and follow tables.( The first letter/s encountered in a particular state, can only mean a particular rule). With LR ...
4
votes
1answer
2k views

Is this formal grammar context-free (CFG) but not context-sensitive (CSG)?

I have the following formal grammar: $$G= (\{S,A,B\},\{a,b\},R,S)$$ $$R=\{S \rightarrow A\ |B, A \rightarrow \varepsilon\ | aA\ |bA, B \rightarrow \varepsilon\ |Bb\ | b\}$$ Now, we see, the ...
4
votes
1answer
449 views

What precisely is infinite ambiguity in a grammar?

From what I've read, an example of infinite ambiguity is usually given in a form of a loop: $S \rightarrow aA \\ A \rightarrow B \\ B \rightarrow A \\ B \rightarrow b$ But a grammar is called ...
4
votes
2answers
21k views

Understanding LEADING and TRAILING operations of an operator precedence grammar

I want to understand what the LEADING and TRAILING of non-terminal in an operator precedence grammar physically mean. I am ...
4
votes
1answer
1k views

Non-linear grammars

I look for information about grammars which can be described by a non-linear equation such as a quadratic equation: $\qquad \displaystyle G \to G G a \mid b$ or $\qquad \displaystyle G \to G G \mid ...
4
votes
1answer
3k views

Simplification of CFG

Recently i was studying removal of useless symbols in productions given in Ullman Hopcroft. The grammar goes as follows S-> aAa | aBC A -> aS | bD B - > aBa | b C-> abb | DD D -> aDa In the ...
4
votes
1answer
3k views

What is the advantage of Greibach Normal Form over Chomsky Normal Form?

I wanted to know the pros and cons of Chomsky normal form and Greibach normal form.
4
votes
0answers
53 views

Reference on relating Post systems to string rewriting systems and formal grammars?

wikipedia states: Every Post canonical system can be reduced to a string rewriting system (semi-Thue system). [...] It has been proved that any Post canonical system is reducible to such a ...
4
votes
0answers
53 views

Acyclic Manhattan turtle

There is a grammar that describes the walks of a turtle around Manhattan, such that the turtle always returns home. It is described in the book "Parsing Techniques" by Dick Grune and Ceriel J.H. ...
4
votes
0answers
1k views

Automatic tool for resolving left-recursion within CFG [closed]

Though facing the fear that someone might not like my question but does somebody know a useful tool to either resolve left recursion or to simplify a context-free grammar automatically ? I need to ...
4
votes
2answers
237 views

Context free grammar construction

My problem with CFG is, I am to generally create ones that don't have requirements such as: $\qquad \{a^m b^n \mid m \le n \le 2m \}$ I have no clue where to begin, and how to approach it. I was ...
3
votes
2answers
2k views

Does a context-free grammar with multiple variables have a “starting” point?

So lets consider the following grammar $$ \begin{align*} S &\to 0 \mid 0A \\ A &\to 1 \end{align*} $$ would the string "1" be accepted by the language or must the language start with $S$?
3
votes
2answers
2k views

Proving that a word is *not* generated by a context-free grammar

I saw the answer in one of the solutions and I cannot figure out how they got the answer. The question is asked if the word is in the language or not for CNF... How did they get the answer so that ab ...
3
votes
3answers
4k views

How to convert a context free grammar (could generate regular language) to a right-linear grammar

Consider the context free grammar: $$S \rightarrow aSb \mid aSa \mid bSa \mid bSb \mid \varepsilon$$ It could generate regular language, which means it can be converted to a right linear grammar. Is ...
3
votes
2answers
5k views

Context-free grammar for $\{ a^n b^m a^{n+m} \}$

I've got a problem with this task. I should declare a context-free grammar for this language: $\qquad \displaystyle L := \{\, a^nb^ma^{n+m} : n,m \in \mathbb{N}\,\}$ My idea is: We need a start ...
3
votes
1answer
3k views

Grammar of regular languages vs. context free languages

Let $L$ be some language. What could you say about $L$'s grammar if it is a regular language, that couldn't be said if it was a context free language? For example, in case $L$ is regular, could you ...
3
votes
3answers
2k views

How to represent whitespace in a context-free grammar?

Say we want to support: xx The following grammar does accept it: S -> xAx A -> ε. because S => xAx => xx. But what about supporting: x x I realize this might be a stupid question but I'm really ...
3
votes
3answers
374 views

Formal language without grammar

Definitions: Alphabet $Σ$: finite, non-empty set Language: subset of $Σ^*$ Grammar: Unrestricted grammar (Chomsky Type 0) Language of a grammar: all words that can be produced by applying $P$ ...
3
votes
1answer
3k views

Does transforming a CFG to Chomsky normal form make it unambiguous?

Does transforming a CFG to Chomsky normal form make it unambiguous? And if not, is there a technique to convert a CFG G to an equivalent CFG G', so that G' is both unambiguous and LL(1)?
3
votes
2answers
251 views

Correspondence between automata and formal grammars?

From Wikipedia Since there is a one-to-one correspondence between linear-bounded automata and such grammars, no more tape than that occupied by the original string is necessary for the string ...
3
votes
2answers
3k views

Finding the grammar type of the programming language

How can someone find what type of grammar for a given programming language? Formerly I'm looking for a grammar type for most popular programming languages: C, C++, C#, Java, List, OCaml, Haskell etc.
3
votes
3answers
3k views

Is this language LL(1) parseable?

I tried to find a simple example for a language that is not parseable with an LL(1) parser. I finally found this language. $$L=\{\,a^nb^m\mid n,m\in\mathbb N,\>n\ge m\,\}$$ Is my hypothesis true ...
3
votes
2answers
956 views

non LL(1) grammar but LL(1) language

I'm reading a Basics of Compiler Design and on page 84 it is making the following statement: A language may well be LL(1) even though the grammar used to describe it is not. Can someone give ...
3
votes
1answer
1k views

How can I check that the language of one context-free grammar is a subset of a second context-free grammar?

Could you explain me, how can I check, that the language of first context-free grammar (G1) is a subset of the language of second context-free grammar (G2). G1 and G2 are two LL(1) grammars with ...
3
votes
2answers
268 views

Figuring out the language of a non-linear CFG

I have the CFG G with the following production rules: $$ S \to aSaS \mid b $$ Is it possible to find $L(G)$? I have no idea how describe it by any pattern. I use grammophone to check example words, ...
3
votes
1answer
1k views

Grammar for a language: odd length, middle character not repeated

Consider the following language over the alphabet $\mathcal{A} = \{a,b,c\}$: $$L = \left\{w \in \mathcal{A}^* \mid \text{\(|w|\) is odd and the middle character in \(w\) occurs nowhere else in \(w\)} \...
3
votes
2answers
771 views

Pascal FOR loop with context free gramar

In Pascal For-do loops, there is a rule stating that one cannot modify the counter variable inside the body of the loop. To exemplify the rule, take the following Pascal ...
3
votes
2answers
4k views

Context Free Grammar for $a^*b^*c^* - \{a^n b^n c^n \mid n \geq 0 \}$ [duplicate]

I'm having trouble constructing a Context Free Grammar for the following language: $$a^{\ast}b^{\ast}c^{\ast} - \{a^{n} b^{n} c^{n} \mid n \geq 0 \}$$ I believe it's telling me that no string can be ...
3
votes
1answer
955 views

How to call something that can be either a terminal or a nonterminal?

I had written a compiler compiler a few years ago and I'm now cleaning it up, improving it, and turning it into C. I came across a terminology problem however that I remember in the past I couldn't ...
3
votes
1answer
110 views

Why is this language a regular language?

Came across this in a book, and I'm wondering why the following language is regular? $$ L = \{a^nww^R: n \geqslant 0, w \in \{a,b\}^3\}$$ Is it correct to say that $$ \{a^n : n \geqslant 0\} $$ is a ...
3
votes
2answers
336 views

How to prove the equivalence of two CFG for balanced parentheses?

Given two CFGs for balanced parentheses. $S \rightarrow SS \mid (S) \mid \epsilon$ $S \rightarrow S(S)S \mid \epsilon$ How do I show that they are equivalent? I have been able to show $ L(2) \...
3
votes
1answer
169 views

LL grammars and left-recursiviity

Why LL(k) and LL(∞) are incompatible with left-recursion? I understand that a LL(k) language can support left-recursivity provided that with k-overahead tokens can be resolved any ambiguity. But, with ...
3
votes
4answers
7k views

A context-free grammar for all strings that end in b and have an even number of bs

I'm trying to find CFG's that generate a regular language over the alphabet {a b} I believe I got this one right: All strings that end in b and have an even number of b's in total: $\qquad S \to SS \...
3
votes
2answers
2k views

CFG for language of all palindromes whose number of 1s is divisible by 3

The question is the following: Construct a CFG for $L_2 = \{w \in \{0, 1\}^* \mid w = w^R\text{ and the number of 1’s in $w$ is divisible by 3}\}$. I can construct a CFG for $\{w \in \{0,1\}^* \...
3
votes
1answer
180 views

Find a regular grammar that generates words with even number of a's

I have a language $L$ = {$vabu$ | $v$,$u\in \{a,b\}^*$, $|vu|_a = 0$ $($mod $2)$$\}$ where $|vu|_a$ is number of $a$ in $vu$. I came up with these rules: $\sigma \rightarrow aa\sigma | ab\xi$ $\...
3
votes
2answers
1k views

Examples for CFG that cannot be expressed by regular language

There are nice examples for context free grammars which cannot be expressed with regular language, for example the palindrome and a similar contrived example here, but they are very intuitively ...
3
votes
1answer
71 views

Understanding this answer: A CFG defines a language as a the smallest solution to a system of language equations

Statement comes from this answer. A blanket statement that this is a well-known fact is made in this other question. I have never heard of a language equation. But I am just a student. Given the ...
3
votes
1answer
106 views

Prove that if you can derive w from α in n steps, it's possible with n left-derivations as well

My university's automata theory book claims that the following claim can be proved by induction but it doesn't bother showing the proof. I've tried to prove it myself but I got stuck at the ...
3
votes
1answer
2k views

An example of a non-regular grammar for a regular language?

I understand that a regular language can be specified by either regular or non-regular grammars. What is an example of a non-regular grammar for a regular language?
3
votes
1answer
36 views

Minimizing DFA built on set of words

A set of English words is given. Is there linear or sublinear algorithm to build minimal DFA for the given dictionary? I tried different approaches, and they all were concerned with building Trie and ...
3
votes
2answers
192 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.
3
votes
1answer
140 views

Is $\{ w_1cw_2 \mid w_1 ≠ w_2 \}$ a context-free language?

Is the language $L_1 = \{w_1cw_2 ~|~ w_1,w_2 \in \{a,b\}^{\ast} \text{ and } w_1 \neq w_2\}$ a context-free language? It certainly isn't regular, but is it context free? I'm having trouble creating ...
3
votes
1answer
52 views

Create a grammar that generate the language a^n . b^m . c^q . d^p such that n + p = q + m

I'm stuck on this question. I'm struggling on how to keep track of the number of a and d I have generated. The professor hasn't given the correction. I have seen similar questions but the condition ...
3
votes
1answer
64 views

How to explain/understand brackets of applicative functor [[f u1… un]]?

I am reading article about Applicative Abstract Categorial Grammars http://okmij.org/ftp/gengo/applicative-symantics/AACG.pdf and this article uses brackets [[...]] for action on terms inside ...

1 2 3
4
5
21