Questions tagged [formal-grammars]

Questions about formal grammars, generative descriptions of formal languages.

Filter by
Sorted by
Tagged with
1
vote
1answer
355 views

Parse Trees and Operator Precedence

I have the following basic BNF grammar: ...
0
votes
0answers
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 ...
3
votes
1answer
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 ...
1
vote
1answer
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 ...
0
votes
1answer
874 views

Why is this grammar an LL(2) grammar?

I had a question regarding LL($k$) grammars. I came across a problem that I attempted to solve, but my answer varied from the solution and I wasn't sure why. $$L = \{a^{n + 2}b^mc^{n + m}\ :\ n \ge 1,...
0
votes
1answer
501 views

Does adding S->SS in a context-free grammar change the language to its Kleene star?

Let $L$ be the language generated by a context-free grammar whose start variable is $S$. Does adding $S \rightarrow SS$ in this grammar creating language $L^*$, why? What about grammars in Chomsky ...
0
votes
0answers
38 views

Prove this Context-Free Grammar is Ambiguous

so I have a problem on one of my computational structures final reviews, and I cannot seem to figure it out. It's been driving me crazy, so I would like to post it here for some insight. Prove that ...
-1
votes
2answers
52 views

Context-free grammars for two languages

How do I write context-free grammars for the following languages? $B_2 = \{0^n1^n \mid n > 0\} \cup \{0^n1^{2n} \mid n > 0\}$ $B_3 = \{a^nb^mc^k \mid k = n+m\}$ Can someone help me? I'm not ...
3
votes
1answer
241 views

This doesn't seem like a valid regular grammar; my instructor says it is

The following is a screenshot of a lecture slide from my programming language concepts course: According to Wikipedia and other sources, a regular grammar is one that is either left linear or right ...
-2
votes
1answer
39 views

Context free languages [closed]

I have stumbled on this question: Which of the following languages over the alphabet ${a,b,c,d}$ are context-free and which not ? a) $L_{1} = \{wa^{3n+1}b^nw^{R} \mid w\in \{c,d\}^*,\ n>0\}$; b)...
5
votes
2answers
475 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 ...
1
vote
1answer
76 views

If a Triple Graph Grammar rule counts as a Mathematical Proof

I am intrigued by Triple Graph Grammars (TGG) as a potential for formal mathematical proof. Triple Graph Grammars (TGGs) are a technique for defining the correspondence between two different ...
5
votes
1answer
383 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 ...
0
votes
0answers
18 views

Regular grammar question [duplicate]

Define a regular expression such that there is a string of 1 or more a's continuous followed by a continuous string of b's so that the number of a's and b's are the same. I have ideas on how i would ...
0
votes
2answers
1k views

Making a CFG for a^i b^j c^k such that i+j = 3k

I have the language $L = \{a^i b^j c^k \mid i+j=3k\}$, however I am struggling to convert it to a CFG. I have made it into a PDA fairly easily, its just now getting this to the CFG which is the issue....
1
vote
1answer
92 views

What do two non-terminal symbols on the left hand side of a BNF grammar mean?

I'm learning BNF, and the text I'm using gives a simple grammar for integer expressions like this: ...
1
vote
1answer
79 views

How do I build a left derivation tree from an expression including right-to-left associativity?

Suppose I want to make a left derivation tree of an expression, but the expression includes operators that are right-to-left associative. Would I still expand the left-most variable first in my tree? ...
0
votes
0answers
143 views

When proof by induction on length string is not possible?

I found out an exercise where you have to prove the correctness of the following CFG: Let $L=\{ 0^i 1^j|2i \leq j \leq 3i \}\:$ and $\: G: S\rightarrow 0S11 | 0S111| \epsilon$ claim: Every string $w ...
-1
votes
1answer
77 views

Write a grammar for a language $L=\{ba^{2^n}b |n\ge 1\}$ [closed]

Write a grammar for a language $$L=\{ba^{2^n}b | n\ge 1\}.$$ It's not even context-free as I think. I just can't produce it, although I've tried a lot. Now my best attempt is: \begin{aligned} S &\...
1
vote
1answer
473 views

Proving that a context-free grammar is unambiguous [duplicate]

I have to find an unambiguous context-free grammar that generates the following language. $$L= \{ w \in \{a,b\}^+ : |w|_a = |w|_b\}$$ I think I have found the context-free one, it should be this one. $...
0
votes
1answer
60 views

Does this constitute as an LL grammar?

For the language, $L(aa^*ba) \cup L(abbb^*)$ and the grammar \begin{align*}S&\to aAba \mid abbB\\ A &\to Aa \mid \lambda\\ B &\to Bb \mid \lambda \end{align*} Would the grammar above ...
2
votes
0answers
37 views

Give LL grammar for this language?

I need to give the LL grammar for the language below and explain why the grammar is LL and what the value of $k$ should be: $$L = \{ a^n c^m c^{n+m} : n \ge 1, m \ge 1 \}. $$ I have the following, ...
0
votes
0answers
78 views

Operator-precedence grammar

I can't get what is the operator-precedence grammar... I need to convert this grammar to the grammar of weak precedence but I can't get it even. What does this notation mean ...
1
vote
0answers
109 views

Is star closure of reverse of grammar equivalent to reverse of closure of that grammar

I need to proof if that it's true or not. $ (G^R)^* = (G^*)^R $ If $G$ is a CFG and $ G = \langle V, \Sigma, \delta, S \rangle $ where $ V $ = Set of Variables or Non-Terminal Symbols $ \Sigma $ = ...
1
vote
1answer
57 views

Problem with forming a context-free grammar describing a language

I've been trying for hours to figure out, how to form a CFG describing this language $L$: $$L=\{ w\in\{a,b\}^* \mid w\text{ is of the form }a^nxb^{n+2}\text{, where }x\text{ is a string of length }3\...
0
votes
0answers
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 ...
2
votes
1answer
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 ...
1
vote
1answer
200 views

Prove that the language $L_1 = \{a^ib^{2i}c^j \;|\; i,j ≥ 0\}$ is context-free

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 ...
2
votes
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 ...
2
votes
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$, ...
2
votes
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 ...
1
vote
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 ...
0
votes
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 ...
1
vote
1answer
40 views

Applying BNF rules to themselves?

Say we have some BNF rules for example: $$A ::= B C$$ $$Dx ::= ExFx$$ $$x ::= 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 $...
1
vote
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: ...
0
votes
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 ...
2
votes
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/...
0
votes
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 ...
3
votes
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: ...
2
votes
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 ...
1
vote
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(...
0
votes
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 \...
1
vote
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 ...
1
vote
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-...
0
votes
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 ...
2
votes
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 ...
2
votes
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 ...
2
votes
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 \epsilon$ $B \to aB \mid bB \mid \epsilon$ Is the above language context-free? The above language looks like $\{ w \in (...
1
vote
1answer
627 views

Is the complement of every non Turing recognizable language a Turing recognizable language?

One thing I understand is that the complement of every Turing recognizable(but not decidable) language is non Turing recognizable. What about the complement of non Turing recognizable language? Is ...
1
vote
2answers
94 views

What is the difference between language hierarchy and Grammar hierarchy for LL and LR?

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