# Questions tagged [formal-grammars]

Questions about formal grammars, generative descriptions of formal languages.

938 questions
Filter by
Sorted by
Tagged with
355 views

### Parse Trees and Operator Precedence

I have the following basic BNF grammar: ...
150 views

### Conversion from automaton to left linear grammar

I stumble across this problem: Give right linear grammar. The solution given was simple: $S\rightarrow bA$ $S\rightarrow aS$ $A\rightarrow \lambda$ $B\rightarrow bA$ $A\rightarrow aB$ Earlier ...
1k 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 ...
76 views

### Context Free Grammar $L = \{a^i(b+c)^jd^k | i<j+k; i,j,k>0\}$

I'm trying to design a CFG that accept the words of the following language: $$L = \{a^i(b+c)^jd^k \mid i<j+k; \quad i,j,k>0\}$$ My first approximation would be to do $i = j+k$ as something ...
874 views

28 views

### Name for a property of grammars

Parsing s-expressions is almost trivial. This is true for both automated processes (and thus implies ease of implementation of such processes) and for a human readers of printed s-expressions. It is ...
194 views

### Should we eliminate left recursion before using NPDA to simulate CFG?

I read the book "Introduction to the Theory of. Computation, Third Edition by Michael Sipser". It says: If a language is context free, then some pushdown automaton recognizes it. Let A be a ...
200 views

Prove that the language $L_1 = \{a^ib^{2i}c^j \;|\; i,j ≥ 0\}$ is context-free. I have a grammar like this but there are some strings that are not be able to be generated \begin{align} S &\to ... 1answer 39 views ### Formalism for unambiguous context-sensitive languages? I know that there are some languages that are unambiguous but not context-free (this is a good fact). Is there any kind of formalism for describing unambiguous context-sensitive languages? Even better ... 0answers 82 views ### Looking for a subclass of deterministic context-free languages, other than the subclass of regular languages Let X=\{x_1,\ldots,x_n\} be a finite set of alphabet and X^\ast denote the set of all words (including empty word) over X. Clearly, X^\ast is a regular language. Is there a subclass, say C, ... 1answer 151 views ### Conversion of ambiguous left recursive grammar to LL(1) I have been strugling with this LL(1) transformation for far longer than expected and am getting quite desperate. We are given a grammar  G = \left\{V_N, V_T, S, \Phi \right\}, with the non-terminal ... 2answers 104 views ### CFG - Left factoring in recursive nested productions I'm attempting to convert a CFG into an LL(1) grammar for predictive parsing in a compiler. I've been able to left factor and eliminate left recursion and ambiguity for every case in the grammar, with ... 0answers 81 views ### Grammar/Chomsky-Type for L = \{ww \mid w \in \{a,b\}^*\} [duplicate] I've been given the following task and have tried a few things, but none seem to result in what is required. L = \{ww \mid w \in \{a,b\}^*\} What Chomsky-Type is L? Provide a grammar fulfilling ... 1answer 40 views ### Applying BNF rules to themselves? Say we have some BNF rules for example:A ::= B CDx ::= ExFxx ::= y So we might start with $Dx$ and apply rule 2 to get $Ex Fx$ and then apply rule 3 to get $Ey Fy$. But starting with $... 0answers 57 views ### Constructing Context Free Grammar with 3 terminal symbols, with two dependent pairs I am new to Context Free Grammars and am having trouble wrapping my head around how to approach writing a CFG for the following language: ... 1answer 35 views ### Explain why a language can be generated by a context free grammar [duplicate] I have a problem where I am asked to explain why the language that has words made of$a$and$b$such that the number of$a$'s is equal to the number of$b$'s, can be generated by a context free ... 0answers 16 views ### Induction / (machine learning) of Resource Grammars for Grammatical Framework? Grammatical Framework is based in Abstract Categorial Grammars. It is known that Combinatory Categorial Grammars have grammar induction/learning capabilities see e.g. https://link.springer.com/article/... 1answer 140 views ### CFG to PDA - no empty transitions Working for my exam, this question popped up. Given the production rules below, draw a pushdown automaton to recognise the language it generates: S → AB A → BA B → BB B → T T → b ... 1answer 164 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: ... 0answers 83 views ### How to prove that a language created from a context-free gramar's left side is regular(or left-linear)? Given a context-free grammar$G$, let$\longrightarrow_G$be the (one-step) rightmost derivation relation, and$\longrightarrow^*_G$its reflexive and transitive closure. Let$S$be the start symbol ... 1answer 184 views ### L(G) = ∅ is undecidable? For a grammar$G$, why is the problem of whether$L(G)=\emptyset$is undecidable? I'm confused as, for recursive languages there exists a Turing machine which will halt every time and give an answer(... 1answer 28 views ### Which language is produced by this grammar? I was asked to define the language which is produced by the following grammar:$G = (V, \Sigma, S, P)V = \{S, A, B\}\Sigma = \{a, b, c\}$\begin{equation} P= \begin{cases} S \... 0answers 172 views ### Unrestricted grammar is closed under intersection I want to show that unrestricted grammar is closed under intersection and I don't want to use Turing machine or etc. So I think that we have two grammar$G_1$and$G_2$that are restricted for example ... 0answers 52 views ### Examples of context-free grammars whose ambiguity is unknown Are there any examples of context-free grammars for which we simply do not know whether they are ambiguous? By examples I mean an actual specification for the grammar, not some kind of non-... 4answers 332 views ### Grammer Class/Production Rules of Programming Languages I'd read around on the interwebs, and a lot of the text indicated that many programming languages are generated by a context-free grammar, which leads me to 2 questions: Doesn't variable scoping ... 0answers 237 views ### Context-sensitive grammar for language$L = \left\{ww \mid w \in \left\{a,b\right\}^* \right\}$[duplicate] Find a context-sensitive grammar for language$L = \left\{ww \mid w \in \left\{a,b\right\}^* \right\}$where$L \in DCSL \setminus CFL$. I find this task from old exam but there is no solution. I try ... 1answer 206 views ### Are grammars corresponding to DFAs unambiguous and those to NFAs ambiguous? Are grammars corresponding to DFAs unambiguous and those to NFAs ambiguous? According to what I studied, every DCFL is guaranteed to have an unambiguous grammar though there are multiple grammars ... 1answer 342 views ### Is the language given by a context-free grammar always context-free? Consider the language generated by the following grammar:$S \to aSBb \mid \epsilonB \to aB \mid bB \mid \epsilon$Is the above language context-free? The above language looks like$\{ w \in (...
Till now I have believed that a LL language is a language generated by a LL grammar. Same goes for LR. Now I know some of the hierarchies such as $LL(1)\subset LR(1)$. I used to think that the ...