Questions tagged [formal-grammars]

Questions about formal grammars, generative descriptions of formal languages.

Filter by
Sorted by
Tagged with
7
votes
3answers
15k views

Regular Expression to Context-Free Grammar

Anyone knows if there is an algorithm for directly write the context-free grammar that generates a given regular expression?
7
votes
5answers
1k views

Relationship between formal system and formal languages

In a course of computer science it is common to study the hierarchy of formal languages, grammars, automata and Turing machines. I wonder what is the relationship of these objects with formal systems. ...
7
votes
1answer
7k views

Relation between simple and regular grammars

I am reading "An Introduction to Formal Languages and Automata" written by Peter Linz and after reading the first five chapters I face below problem with simple and regular (especially right linear) ...
7
votes
2answers
5k views

Converting to CFG from a CFL? [duplicate]

I am trying to learn CFG. Now to make a CFG from a CFL it is really difficult for me. Is there any simple rule or steps so that I can easily find a CFG for a CFL. I am trying to solve one problem ...
7
votes
1answer
16k views

Left recursion and left factoring — which one goes first?

if I have a grammar having a production that contains both left recursion and left factoring like $\qquad \displaystyle F \to FBa \mid cDS \mid c$ which one has priority, left recursion or left ...
7
votes
1answer
484 views

Are these valid counterexamples to proofs for CF languages with Non-CF complements?

Someone asked for examples of context-free languages with non-context-free complements. The first answer says: The language $L_1= \{ww \mid w \in \{a,b\}^*\}$ is not context-free (as can be shown ...
7
votes
3answers
2k views

How to generate a context sensitive grammar for www

I am trying to solve for my exam coming up and have no clue how to generate the grammar for Context sensitive languages for example how do i proceed on this kind of question. Give a context-...
7
votes
2answers
11k views

Context Free Grammar for {a^ib^j | i,j ≥ 0; i ≠ 2j}

Can someone help with this: $L=\{a^ib^j \mid i,j \ge 0 \text{ and } i \ne 2j\}$ I'm trying to write a grammar for this language? I don't know how to do this. I tried this: $S \rightarrow aaAb \...
7
votes
1answer
511 views

Convert PEG to BNF

Parsing expression grammars (PEGs) are unambiguous and have a superficially similar syntax to BNF, but include three important differences: The ordered choice operator ...
7
votes
2answers
674 views

Generating a set of minimal-length strings that, together, invoke every production of a context free language

Problem (tl;dr) Given a context free grammar, $G$, find a set of strings that take $G$ through every production it has at least once. How and how fast can it be done? Background I'm working on a ...
7
votes
1answer
521 views

What real-world computer languages cannot be described by deterministic grammars?

Are there any examples of real-world computer languages that are non-deterministic? By computer languages I include programming languages, markup languages, query languages, modeling language, ...
7
votes
1answer
578 views

How to convert a non-embedding context free grammar to regular grammar?

Please note that I am aware the undecidability of the conversion of context-free grammar to regular grammar. But given the non-embedding property of the input context-free grammar, is there any ...
7
votes
1answer
935 views

reduce reduce and shift reduce error in LALR grammar

I have to write a grammar for Pascal, and there is just one thing that is causing problems. Lets say we have operators (sorted by priority from low to high): Postfix ...
6
votes
3answers
1k views

Context-free grammar for $L = \{a^{2^k}, k \in\mathbb{N}\}$

In an exercise, I am asked to find a context free grammar for language $L = \{a^{2^k}, k \in \mathbb{N}\}$. I have been trying to use a "doubling" variable. If $a^{2n} \in L, n\in\mathbb{N}$ then use ...
6
votes
2answers
6k views

Is it decidable whether a given context free grammar generates an infinite number of strings?

Is the decision problem "Does a given context free grammar generate an infinite number of strings" decidable? In order to test whether a context free grammar generates an infinite number of strings or ...
6
votes
4answers
376 views

Why does $A(L)= \{ w_1w_2: |w_1|=|w_2|$ and $w_1, w_2^R \in L \}$ generate a context free language for regular $L$?

How can I prove that the language that the operator $A$ defines for regular language $L$ is a context free language. $A(L)= \{ w_1w_2: |w_1|=|w_2|$ and $w_1, w_2^R \in L \}$, where $x^R$ is the ...
6
votes
2answers
44k views

Different between left-most and right-most derivation [duplicate]

I am a beginner started learning theoretical computer science. I just came through context-free grammars. So my question is: what is the different between left-most and right-most derivation? ...
6
votes
2answers
3k views

In context-free grammar (CFG), what is the importance of doing both leftmost and rightmost derivations?

I am a beginner learning theoretical computer science. While learning about CFG, I found that doing both leftmost and rightmost derivations gave me the same parse tree. So, my question is: Why is it ...
6
votes
1answer
12k views

Left-Factoring a grammar into LL(1)

I have a homework assignment where I need to convert a grammar into LL(1). I've already removed the left recursion, but I'm having trouble doing left-factoring. All of the examples I've found are ...
6
votes
2answers
295 views

any hope for a universal automatic parser?

Say you are a program, and you are given some source code but you don't know in what language, it can be C++/Java/Python/Lisp/... all you know is that it is highly structured and LR(1) parse-able, and ...
6
votes
4answers
134 views

Minimal size of a context-free grammar which defines $L_n=\{a^k\mid 1\le k\le n\}$

I am looking for the minimal size of a context-free grammar which defines the finite language $$L_n=\{a^k\mid 1\le k\le n\}.$$ The size of a grammar is defined as the total length of all right-hand ...
6
votes
1answer
241 views

Are these special (one production) Context-Free Grammars always unambiguous?

Consider the following (Context-Free) Grammars with only one production rule (not including the epsilon production): $S \rightarrow aSb\;|\;\epsilon$ $S \rightarrow aSbS\;|\;\epsilon$ $S \rightarrow ...
6
votes
1answer
1k views

Closure properties of linear context-free languages

Under what operations are linear context-free languages closed? Suppose $L_1, L_2$ are two linear context free languages. Are there any guarantees about $L_1 \cup L_2$, $L_1 \cap L_2$, $\overline{L_1}...
6
votes
3answers
211 views

Prove that the complements of pumping-style languages are context-free

Define $L = L(u,v,x,y,z) = \{uv^ixy^iz : i \geq 0\}$, with $u,v,x,y,z \in \Sigma^*$. Prove that $\overline{L}$ is a CFL for all $u, v, x, y, z$ Clearly, $L$ is a CFL, as it is generated by the ...
6
votes
2answers
310 views

Grammatical characterization of deterministic context-free languages

Deterministic context-free languages are commonly defined using an automaton concept, the (restricted, deterministic) pushdown automaton. To some that is confusing, as the name context-free refers to ...
6
votes
1answer
287 views

Determining whether a CFG is $LL(k)$ for any $k$?

In Knuth's original paper on $LR(k)$ grammars, he proved that the decision problem "Given a CFG $G$, is there a $k$ such that $G$ is an $LR(k)$ grammar?" is undecidable. Is there a similar result ...
6
votes
2answers
165 views

Computing follow sets conservatively for a PEG grammar

Given a parsing expression grammar (PEG) grammar and the name of the start production, I would like to label each node with the set of characters that can follow it. I would be happy with a good ...
6
votes
1answer
236 views

Expressive power of formal systems

How do we classify formal systems' (propositional logic, first-order logic, second-order logic, higher-order logic, Hoare logic and type theory) expressivity? In the same way that grammars (CSG, ...
6
votes
1answer
640 views

What would a formal grammar for a binary file format look like?

Binary structures often feature length specifiers; the parser is supposed to read them and then consume the specified amount of symbols. Because of this, the grammar is context-sensitive. What would ...
6
votes
1answer
339 views

Will this algorithm terminate on any input?

One can compress data with straight-line grammars. An algorithm that employs this technique is called Sequitur. If I understood correctly, Sequitur basically starts with one rule representing the ...
6
votes
1answer
78 views

When is ε-removal from a CFG idempotent?

For which context-free grammars is it idempotent to remove $\varepsilon$-productions? Given that there are multiple rewriting algorithms which preserve language and leave the grammar without $\...
6
votes
1answer
309 views

Why is ww a linear indexed language while www is not?

I am a little bit confused on one idea regarding indexed languages. $\{ww \mid w \in \{a,b,c\}^* \}$ is a linear indexed language, but $\{www \mid w \in \{a,b,c\}^* \}$ is not a linear ...
6
votes
1answer
562 views

Can this CFG be written into an equivalent LL(1) grammar?

I have the following CFG which I suspect cannot be rewritten to one which is LL(1): $S \rightarrow \epsilon\ |\ aSbS\ |\ bSaS\ |\ cSdS\ |\ dScS$ I've thought about it for a while, and can't seem to ...
6
votes
0answers
64 views

Is THEADS the same as FIRST?

I'm reading the paper "A Practical General Method for Constructing LR(k) Parsers" by David Pager, and it contains the following paragraph: We will first of all briefly review the LR(1) parsing and ...
5
votes
2answers
1k views

does every CFL have an ambiguous CFG?

some questions have been popping up recently on ambiguity in CFLs/CFGs which can have subtleties (eg languages vs grammars & ambiguity vs inherent ambiguity). wikipedia states: Many [context ...
5
votes
3answers
130 views

How do I calculate the Nth result of a context-free grammar?

Given a context-free grammar and a maximum depth, how do I directly compute the Nth sentence without calculating or caching intermediary sentences? Take as an example the following grammar: (from ...
5
votes
1answer
986 views

Chomsky normal form and regular languages

I'd love your help with the following question: Let $G$ be context free grammar in the Chomksy normal form with $k$ variables. Is the language $B = \{ w \in L(G) : |w| >2^k \}$ regular ? ...
5
votes
2answers
421 views

Why is the start symbol “not allowed” on the right hand side in Chomsky normal form?

I had a question regarding CNF (Chomsky normal form) in formal language theory. I noticed that a lot of authors (including my own professor, and the Wikipedia page for CNF) frown upon or don't allow ...
5
votes
1answer
216 views

Hardness of ambiguity/non-ambiguity for context-free grammars

A grammar is ambiguous if at least one of the words in the language it defines can be parsed in more than one way. A simple example of an ambiguous grammar $$ E \rightarrow E+E \ |\ E*E \ |\ 0 \ |\ ...
5
votes
1answer
2k views

Example of unrestricted grammar which produces non-context-sensitive language

I'm talking about Type-0 (Chomsky hierarchy) unrestricted grammar, where production rules of grammar are of the form $\alpha\rightarrow\beta$, where $\alpha,\beta\in N\cup\Sigma$. I can not find any ...
5
votes
2answers
865 views

How to get 2-state PDA for CFG?

I'm studying for my Computing languages test and there's one idea I'm having problems wrapping my head around, as far as I know for any Context Free Grammar (CFG), we can design a 2-state Pushdown ...
5
votes
1answer
582 views

Can every linear grammar be converted to Greibach form?

Can every linear grammar be converted to a linear Greibach normal form, a form in which all productions look like $A \rightarrow ax$ where $a \in T$ and $x \in V \cup \{\lambda\}$? ($T$ is the set of ...
5
votes
3answers
2k views

Proving a grammar only generates words whose alternating digit sums are multiples of three

This is homework and I'm looking for a push in the right direction. Proofs were never something I was properly taught, so now they're kind of a weak point. Here's the problem: The following ...
5
votes
1answer
347 views

Removing lambda-productions when it's at the start symbol

I had a question regarding removing lambda-productions from context-free grammars. I understand that the basic theorem or process for removing lambda-productions is to find nullable productions and ...
5
votes
2answers
120 views

Is there any other computation theory besides the one in automata theory?

I'm a bit confused at a fundamental level. In Computer Science, maybe some of us mostly use discrete mathematics since our computer is digital (like during studying operating system, algorithms, ...
5
votes
2answers
2k views

Unrestricted grammar to generate $a^{n^2}$

I have been asked to find a grammar that will generate the language $\{a^{n^2}:n \ge0\}$ in an exercise. So far I tried to replicate the previously written characters with my grammar rules but it didn'...
5
votes
1answer
17k views

Steps to convert regular expressions directly to regular grammars and vice versa

I came across following intuitive rules to convert basic/minimal regular expressions directly to regular grammar (RLG for Right Linear Grammars, LLG for Left Linear Grammars): Then I came across many ...
5
votes
1answer
268 views

Closure under intersection of context free binary trees

Some sets of ordered binary trees can be represented as a CFG with rules of the form A -> aBC A -> b Where A,B,C are ...
5
votes
1answer
276 views

Generative power and classification of matrix grammars

[Edited] I am reading about matrix grammars from several sources and got confused about its generative power and classification to the Chomsky hierarchy. In here it is stated that: A matrix grammar ...
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|...