Questions tagged [formal-grammars]

Questions about formal grammars, generative descriptions of formal languages.

Filter by
Sorted by
Tagged with
3
votes
1answer
431 views

Show that the string $( [ ) ]$ is not in a Dyck language

I think I understand why the string $( [ ) ]$ is not in a Dyck language. In my words, D2* is all the dyck words of 2 parentheses. From the definiton of $D2*$, every words must have exactly 2 ...
3
votes
1answer
371 views

Indentation based Grammars

Considering programming languages with significant whitespace for indentation, such as Python or Haskell. How does this whitespace fit into the grand schemes of programming language grammars. I can ...
3
votes
2answers
3k views

CFG and PDA for the grammar that has perfectly nested parentheses and brackets

I gotta make a CFG and PDA for the grammar that has perfectly nested parentheses and brackets. $\qquad\begin{align} S &\to [S] \\ S &\to (S) \\ S &\to SS \\ S &\to \varepsilon \...
3
votes
1answer
939 views

Unambiguity of Reverse Polish Notation

Lets say I have given following grammar which generates arithmetic expressions in reverse polish notation: $G=({E},{a,+,*},P,E)$ $P={ E \rightarrow EE+ | EE* | a }$ I know this grammar is ...
3
votes
1answer
197 views

Factor a grammar

Consider the context free grammar: $\qquad \begin{align} \mathrm{bill} &\to \mathrm{items}\ \mathrm{total}\ \mathrm{vat} \\ \mathrm{items} &\to \mathrm{item} \mid \mathrm{item}\ \...
3
votes
1answer
24 views

How to split a context-free language into three sub-languages?

I try to split the language $$ L = \{a^ib^j \mid i \neq 2j, i \neq 3j\} $$ into three languages \begin{align} L_1 &= \{a^ib^j \mid i < 2j\} \\ L_2 &= \{a^ib^j \mid 2j < i < 3j\} \\ ...
3
votes
1answer
79 views

Are the languages $\{w\in \{a,b\}^* : \#_a(w) > \#_b(w) \}$ and $\{w\in \{a,b\}^* : \#_a(w) \neq \#_b(w) \}$ context free?

So at the beginning I was aiming at $L_{a\neq b} = \{w\in \{a,b\}^* : \#_a(w) \neq \#_b(w) \}$. But figured out that is would be better to first deal with: $L_{a>b} = \{w\in \{a,b\}^* : \#_a(w) &...
3
votes
1answer
157 views

What is the grammar for language $L={a^nb^m : n \neq m-1}$?

What is the grammar for language $L = \{ a^nb^m : n\neq m-1\}$? I only know I have to write grammar for both $ n<m-1 $ and $ n>m-1 $, so this is what I wrote: ...
3
votes
1answer
2k views

How to eliminate context-free grammar's ambiguity

I want to write a CFG that generates the words over {a,b} with the same number of ocurrences of a's and b's. I have come up with a couple of possibilties so far. I think they're correct but they're ...
3
votes
1answer
415 views

Where does LL parser belong in the top-down parsers classification

There are four types of top-down parsers according to this answer: recursive descent backtracking recursive descent predictive table-driven with backtracking table-driven predictive. Also the author ...
3
votes
2answers
2k views

Bottom-Up Evaluation of Inherited Attributes

I came across $2$ translation schemes of Syntax Directed Translation (SDT) in compilers which are as follows : Using a top-down translation scheme, we can implement any $L$-attributed definition ...
3
votes
1answer
246 views

Is unrestricted grammar equivalent to deterministic Turing machine?

Suppose we have unrestricted grammar but with restrictions on how rules are applied: we take first rule, search in string left to right and apply it as we go. If no match found, we proceed with second ...
3
votes
1answer
128 views

Is $\{a^nb^n\}\cup\{a^nb^{2n}\}$ LR(k)?

I was reading Knuth's paper "On The Translation of Languages from Left to Right", my particular interest being on RL($k$) languages (not a typo). By the end of the paper, he puts the grammar: $$ S \...
3
votes
1answer
2k views

Ambiguous Grammar and SLR parsing table : No conflicts?

We have been studying the development of SLR parsers, and that now we have done the arithmetic expression grammar (the unambiguous version), I was curious to see if the same could be done to the if-...
3
votes
3answers
169 views

Compression of non-adjacent structure using grammar

I'm working with compression algorithms that use context-free grammars (e.g. RE-PAIR and SEQUITUR). These grammars look for frequently occurring digrams (pairs of adjacent symbols) in an input string ...
3
votes
1answer
1k views

Is this an example of a type-0 grammar that is not context-sensitive?

A type-0 grammar generates a recursively enumerable (RE) language. A RE language is also known as a semi-decidable language. A semi-decidable language is a particular kind of undecidable language: ...
3
votes
1answer
274 views

Lookahead set: Determining minimum $k$ such that $G$ is a strong $LL(k)$ grammar

How do we determine minimum $k$ such that $G$ is a strong $LL(k)$ Grammar Like for grammar $G$ with the following rules $S\rightarrow aAcaa \mid bAbcc,A\rightarrow a \mid ab \mid \epsilon$
3
votes
1answer
46 views

How to define at least one occurrence of a string between two tokens in bottom up LALR(1) parser grammar

I am trying to define a non terminal symbol in a LALR(1) grammar (with CUP parser). It is requested that ...
3
votes
1answer
945 views

Is the ambiguity of a regular tree grammar decidable?

Is there an algorithm which decides whether a regular tree grammar $G$ is ambiguous, i.e. there exists a tree $t\in L(G)$ which can be parsed by the grammar in more than one ways, using only leftmost ...
3
votes
2answers
481 views

Construct a context-free grammar for a given set of words

I have seen a few years back a nice and simple algorithm that, given a (finite) set of words in some alphabet, builds a context-free grammar for a language including these words and in some sense "...
3
votes
1answer
4k views

Context-free grammar to a pushdown automaton

I'm trying to convert a context free grammar to a pushdown automaton (PDA); I'm not sure how I'm gonna get an answer or show you my progress as it's a diagram... Anyway this is the last problem I have ...
3
votes
1answer
994 views

Understanding application of Arden's theorem to find regular expression

I learnt Ardens theorem and its usage as follows: Ardens Theorem Let $P$ and $Q$ be two regular expressions over alphabet $Σ$. If $P$ does not contain null string, then $R = Q + RP$ has a ...
3
votes
1answer
588 views

Eliminate left recursion from grammar

Consider the following grammar: $$ A\to Ba|Aa|c \\ B\to Bb|Ab|d $$ How do I convert this grammar to be LL(1) by eliminating direct and indirect left recursion? I have tried applying the ...
3
votes
1answer
73 views

Are there any specific mechanical ways to reduce a regular expression 'equation' to a more simple one?

So if we have a complex equation in regular algebra we can use properties like distrbuivity, associativity and commutativity to make an equation simper or more compact. Can we use some sort of ...
3
votes
1answer
409 views

Do basic operators of RE (Union, Kleene star and Concatenation) have properties like associativity, commutativity, distrbutivity etc.?

So in regular algebra we have some basic operations defined such as multiplication, addition, subtraction and division. For these operations/operators, we have some properties like commutativity, ...
3
votes
1answer
219 views

CFG for words that are not a concatenation of the same word [duplicate]

I am teaching myself formal languages, and yesterday i got stuck at an exercise asking for a context free grammar for the language: $ L = \{x \in \Sigma ^{+} | \ \forall w \in \Sigma ^{+} \ x \neq ...
3
votes
1answer
90 views

Creating a CFG that connects lengths of three blocks [duplicate]

I have to create a CFG which generates $$\{a^n (ab)^n c^m d^\ell e^k \mid n>0, k, \ell, m\ge0, k<m, m=\ell+k\}$$ The first part is easy enough, I came up with $$\begin{align*} S &\to ...
3
votes
1answer
97 views

grammatical complexity of propositional and monadic predicate validities? (and grammars for recursive but not context-sensitive languages?)

Consider two sets: the set of validities of propositional logic and the set of validities of monadic predicate logic. Call the first set $VP$ and the second set $VQM$. Both of these sets are decidable,...
3
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 ...
3
votes
1answer
63 views

Generalized operators for programming languages

After asking this question on stackoverflow, it has changed slightly. Is there a way to represent a grammar as a basis for a vector space and represent a program as an object that lives in that ...
3
votes
0answers
16 views

Base-k representations of polynomials: state of art [closed]

In chapter 4 of Jeffrey Shallit's A Second Course in Automata Theory the following problem is formulated as open: Let $p(n)$ be a polynomial with rational coefficients such that $p(n) \in \mathbb{N}$ ...
3
votes
0answers
100 views

Simple description of circularities in Knuth original attribute grammar paper

Knuth's original attribute grammar paper (title: Semantics of Context-Free Languages) introduced three types of circularity. More specifically section "Testing for circularity" page 134-5 figures 3.1-...
3
votes
0answers
121 views

Semantic parsing with Grammatical Framework - is this possible?

So far I have learned about categorial grammars, type logical grammars and formal semantics of natural language, the relevant tools are Cornell Semantic Parsing Framework https://github.com/clic-lab/...
3
votes
0answers
27 views

How to model grammar ambiguity

Say you have a (context-free) grammar, and you wish to mathematically model the magnitude of the ambiguity possible under this grammar, across the space of all possible** input strings. Practically, ...
3
votes
0answers
183 views

How would I build a parser generator for a context free grammar using Pushdown Automata?

I am building a parser generator, not for any project in particular, just for fun to improve my understanding of parsing, grammars, languages, etc. I am at the point where I have lexer generation ...
3
votes
0answers
100 views

Unambiguous context-free language that can't be parsed in linear time by backtracking recursive descent?

Is there a context-free language that can be expressed with an unambiguous grammar but can't be expressed with a grammar that would result in linear-time backtracking recursive descent parsing? The ...
3
votes
0answers
233 views

How to refactor a grammar to be suitable for recursive descent?

I'm trying to learn how to use a recursive descent parser, and reading on this page I find this example: $S \rightarrow AB \\ A \rightarrow a \\ A \rightarrow SA \\ B \rightarrow b \\ B \rightarrow ...
3
votes
0answers
227 views

Context-free grammar for DAGs?

I'm looking for a "safe" representation of DAGs. With "safe" representation I mean that it can be described by a context-free grammar. Ideally, this grammar would be suitable for a simple LR parser. ...
3
votes
0answers
89 views

What kind of formal language is generated by Parsing Expression Grammars?

I've been unable to find what class of languages is recognized by PEGs. The original paper [1] only conjectures that there are some Context-Free Grammars that are unrecognizable by PEGs. It also ...
3
votes
0answers
115 views

Is there a grammar type for deterministic LBA?

Contextsensitive grammars define exactly the langauges acceptable by nondeterministic LBA. But how about deterministic LBA - is there a grammar type capturing exactly the languages acceptable by this ...
3
votes
0answers
50 views

Tree Languages are Word Languages on an Infinite Alphabet of Contexts

I have been reading the book Tata (Tree Automata Techniques and Applications), and there is a sentence I have read thousands of times, yet still don't quite understand. In the beginning of Chapter 2, ...
3
votes
0answers
317 views

Recursive-descent parser for the grammar S -> S(S)S | ε

I'm studying (for self-betterment - I don't go to school) the 2nd edition of Compilers: Principles, Techniques and Tools by Aho et al. I'm not sure how to do Exercise 2.4.1 (b), which is to construct ...
3
votes
0answers
99 views

Prove or disprove that every $L$ in this class is a CFL iff $L$ is equivalent to a substitution

Let $L$ be a language with every string of the form $(w_i\#)^*$ with $w_i\in\{0,1\}^*$. Set $w'\sim w$ if there is a permutation $\pi_1$ such that $w_i=w'_{\pi_1(i)}$ for all $i$. If additionally $\...
3
votes
2answers
205 views

How to modify semantic actions when removing left-recursion from a grammer

Is there any algorithm that tells us how to modify semantic actions associated with a left-recursive grammar? For example, we have the following grammar, and its associated semantic actions: $ S \...
2
votes
2answers
415 views

Can a Formal Language be of a type (RE, REC, Regular, etc) for one TM, but of a different type for another?

I'm new to the study of formal languages, and I wondered if languages of a certain type are objectively of that type (RE, REC, regular, etc), or if their type varies on their context? I had this ...
2
votes
3answers
2k 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|n,m\in\mathbb N\land n\ge m\}$$ Is my hypothesis true or is ...
2
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)?
2
votes
3answers
1k views

Why is the distinction between linear and context-free grammars useful?

The linear grammar is a grammar that's either left, right or left and right linear. The context-free grammar can contain any kind of productions of non-terminals and terminals. All linear grammars ...
2
votes
2answers
1k views

Can a CFG end have a non-terminal symbol in the middle of it?

What is the correct way to write a CFG? A -> B C' E C' -> C C' -> null or A -> B C' C' -> C E C' -> E
2
votes
4answers
492 views

How to prove that Ambiguity is still present in Resolved Production of Dangling Else Problem?

$\textbf{stmt} \to$ $ \textbf{if} $expr$ \textbf{then}$ stmt $\mid $ $\textbf{if}$ expr $ \textbf{then}$ stmt$ \textbf{else}$ stmt $\mid \textbf{...