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.

Filter by
Sorted by
Tagged with
5
votes
1answer
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|...
5
votes
1answer
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 ...
5
votes
3answers
792 views

Give a grammar to show whether a language is regular or context-free

I have to generate a grammar for the language $L = \{ w \in \{ a, b\}^* \mid |w| \in 2\mathbb{N}, w \neq w^R\}$ and give the type of the language. I've generated the grammar $\qquad \begin{align} ...
5
votes
1answer
53 views

Are there (highly) restricted process calculi? Perhaps similar to formal grammar?

I've started to read about process calculi (such as CSP and π-calculus). It seems to me that they are extremely general and can represent pretty much any concurrent system, many of which will be ...
5
votes
2answers
104 views

Context-sensitive grammars without permutation rules

Permutation rules are called those which are of the form $AB\Rightarrow^*BA$1. It is also proven that permutation rules expand context-free grammars and allow them produce non-context-free languages. ...
4
votes
5answers
3k views

Is the language of Roman numerals ambiguous?

An ambiguous Language is a formal language for which there exists a string that can have more than one meaning (several possible meanings or interpretations). Multiple synthesis structures for a ...
4
votes
4answers
10k views

How to find whether a grammar's language is finite or infinite?

I have this context-free grammar and I want to find out whether its language is finite or infinite. ...
4
votes
3answers
163 views

Do CFGs generate many languages?

Suppose we define a CFG such that it is possible to produce strings of the form $a^nb^n$ (in this case, I would think, we would need epsilon-productions). Then one such $L(CFG)$ is $a^nb^n$. However,...
4
votes
2answers
842 views

Given a language L what can we say about the decidability of whether this language is regular or not?

Can we develop a turing machine which on given a language L as input gives as output whether this language is regular or not?
4
votes
2answers
672 views

What if a formal grammar cannot be terminated?

I'm currently in a class on Computability and we just finished looking at formal grammars before moving onto finite automata. We were given an several examples of a formal grammar, and one stuck out ...
4
votes
2answers
126 views

Is the set of LL(*) grammars the same as the set of CFG grammars?

Is the set of LL(*) grammars the same as the set of context-free grammars?
4
votes
3answers
667 views

Is the set of CFGs that contain all odd and even length words Turing-decidable?

$ALLEVEN_{CFG}$ = {M is a grammar, and L(M) includes all strings of even length in $\Sigma^*$} = {(M): ($\Sigma\Sigma$)* ⊆ L(M)} $ALLODD_{CFG}$ = {M is a grammar, and L(M) includes all strings of odd ...
4
votes
3answers
546 views

Is this grammar really LL(1) while not being LR(1)?

$S \rightarrow S$, $L(G) = \{\}$ LL(1) analysis: We estabilish $FIRST(S)$ to be empty and $FOLLOW(S)$ to be $\{\$\}$. $FIRST(S)$ doesn't contain ε, so the parse table looks like this: ...
4
votes
2answers
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 ...
4
votes
2answers
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.
4
votes
3answers
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.
4
votes
1answer
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. ...
4
votes
2answers
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") ?
4
votes
1answer
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 ...
4
votes
1answer
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 ...
4
votes
1answer
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 ...
4
votes
1answer
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 ...
4
votes
2answers
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 ...
4
votes
2answers
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 ...
4
votes
2answers
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. ...
4
votes
1answer
50 views

Why does this grammar derive into $\beta \alpha ^*$ instead of $\alpha ^* \beta$?

In this video clip the teacher presents a grammar $A \rightarrow A \alpha | \beta$ and after providing the parse tree explains that the regular expression for the language generated is represented as $...
4
votes
1answer
519 views

What is a real-world use-case/need for a left-recursive grammar?

I understand the basics of how left-recursion works, and why some people say it's bad. And I've also ready opinions such as: ...like LL and LR parsing, PEGs are often frustrating to use in practise....
4
votes
1answer
122 views

Context-sensitive grammars for $a^ib^jc^{ij}$ and $a^ib^jc^{i^j}$

I would like to get some help for finding the context-sensitive grammar for the language: $$L_1=\{a^ib^jc^{ij} \mid i,j\geq 0\}.$$ To answer the question before it's written here, yes I've tried to ...
4
votes
1answer
95 views

Method for Creating Any Unambiguous Grammar?

I'm in an undergraduate class where we're studying formal grammars right now. I asked my teacher if there was any known set of rules for creating context free grammars that Was guaranteed to produce ...
4
votes
1answer
192 views

Are there grammar classes between Chomsky level 1 and 2?

Are there any grammar classes which are true subsets of Chomsky level 2 but not equal to level 1?
4
votes
1answer
8k views

Removing Left Recursion from Context-Free Grammars - Ordering of nonterminals

I have recently implemented the Paull's algorithm for removing left-recursion from context-free grammars: Assign an ordering $A_1, \dots, A_n$ to the nonterminals of the grammar. for $i := 1$ ...
4
votes
1answer
276 views

Is it decidable whether a linear language contains a square?

A square is a word of the form $ww$. A linear grammar is a CFG that has productions of the form $A\to uBv$ or $A\to u$ (with lower case symbols corresponding to terminal strings). Question: Is it ...
4
votes
1answer
125 views

Arden's lemma applicability on context free grammars

The Arden's lemma states that there exists a solution to the equation between regular expressions r = sr + t, with r unknown, and it is s*t. I went through some other topics on the forum and I always ...
4
votes
1answer
2k views

What are the meanings of metalanguage and metasyntax and EBNF?

I am trying to understand what BNF, metalanguage, and metasyntax are. From https://proofwiki.org/wiki/Definition:Metalanguage A metalanguage of a formal language is a formal language used to ...
4
votes
3answers
236 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
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 ...
4
votes
1answer
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?
4
votes
1answer
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 ...
4
votes
1answer
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 ...
4
votes
1answer
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 ...
4
votes
1answer
508 views

Finding the language of a context-free grammar?

Given following question: Let $G$ be a context-free grammar, $G=(V, \Sigma, R, S)$, that has start variable $S$, set of variables $V = \{S\}$, set of terminals $\Sigma = \{0, 1\}$, and set of rules $...
4
votes
1answer
140 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
1k 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
405 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
20k 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

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
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. ...
4
votes
0answers
594 views

Which programming languages have a syntax that can be described by deterministic context-free grammars?

This question asks which programming languages have a syntax that cannot be described by deterministic context-free grammars - the answer is "Many [...] including Algol 60, C, and C++". Until ...
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 ...