We’re rewarding the question askers & reputations are being recalculated! Read more.

# Questions tagged [formal-grammars]

Questions about formal grammars, generative descriptions of formal languages.

925 questions
Filter by
Sorted by
Tagged with
2k views

### Equivalence of two context free grammars [for the given example]

I know that in general it is undecidable whether two context free grammars generate the same language, but I have to do this exercise and I am finding myself somewhat stuck: G1: S->e|aB|bA B->bS|...
2k views

### Difference between substitution, morphism, and homomorphism

In closure properties, I got confused between substitution and morphism. 1) According to Wikipedia, string substitution means to map letters in a set of alphabets to languages (possibly in a ...
792 views

80 views

### What is examples of languages to prove the inclusions between families of languages generated by matrix grammars?

$\lambda M_{ac}$ = family of languages generated by matrix grammar with appearance checking and with erasing rules $\lambda M$ = family of languages generated by matrix grammar without appearance ...
104 views

### Anatomy of a production rule

Production is said to be of the form $u \to v$. I want to know if you distinguish $u$ from $v$ giving them some distinguishing names, like LHS/RHS or something alike.
102 views

### How to give a context-sensitive grammar for a^nba^nba^nb?

I am struggling on this problem since days: $L = \{a^nba^nba^nb \mid n \in \Bbb N\}$. I have to give for this language a context-sensitive grammar.
479 views

### How to find unambiguous grammar for palindromes

I am trying to figure out how to make an unambiguous grammar for palindromes over the alphabet {a, b}. I have the following, but it is ambiguous and causes conflicts in yacc. ...
3k views

### unambiguous grammar that produce equal number of a and b

is there any unambiguous grammar on alphabet={a,b} that can produce strings which have equal number of a and b (e.g. "aabb" , "baba" , "abba") ?
91 views

### How to express modalities in lambda calculus - are some extensions required?

Lambda calculus can be used for encoding semantics of natural language, e.g. http://yoavartzi.com/tutorial/ contains full details about semantic parsing of natural language: converting natural ...
47 views

### How to make sense of this context-sensitive production in a textbook? (a typo perhaps?)

In Chapter 1 of Kenneth Slonneger and Barry L. Kurtz's Formal Syntax and Semantics of Programming Languages: A Laboratory Based Approach, an example of its production is given to illustrate the nature ...
72 views

### Language of walks in a grid – context-free?

Consider the infinite two-dimensional grid with integer co-ordinates. A walk in the grid can be represented by a string over the alphabet $\{u,d,l,r\}$, where the letters stand for moving one square ...
210 views

### Do an ambiguous grammar and its corresponding unambiguous version generate the same language?

If I have an ambiguous grammar G and its disambiguated version D. Then which one is true L(D) ⊂ L(G) , L(G) ⊂ L(D) or L(G)=L(D)? As I tried with some examples to transform a grammar to it ...
1k views

### Syntax and formal grammar of a formal language

For a formal language, I wonder what differences and relations are between its syntax and its formal grammar. A formal grammar is a set of formation rules that describe how to generate the strings ...
156 views

### Gyorgy E. ReveszExercise 1.1: Show the grammar $G$ generates the language $L$ [duplicate]

The exercise says "Show that the grammar $G = \langle\{S\}, \{a, b\}, S, \{S \to \lambda, S \to aSb\}\rangle$ generates the language $L = \{a^i b^i \mid i = 0, 1, 2, \ldots\}$." Now, I'm new to ...
239 views

### Priority in formal grammar

From my recitation class, I have the following exercise: $\mathrm{EXP} = 0 \mid 1 \mid b \mathrm{EXP} \mid \mathrm{EXP} a \mid \mathrm{EXP} m \mathrm{EXP}$ The above grammar is ambiguous. ...
50 views

566 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 ...
488 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?
36 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 ...
60 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 ...
672 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 ...
508 views

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.
50 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. ...