Questions tagged [formal-grammars]

Questions about formal grammars, generative descriptions of formal languages.

Filter by
Sorted by
Tagged with
0
votes
1answer
104 views

How to eliminate ambiguity of the follwing CFG?

Consider the following CFG: $S\to AED | F \\ A \to Aa | a\\ B \to Bb | b\\ C \to Cc | c\\ D \to Dd | d\\ E \to bEc | bc\\ F \to aFd | BC$ The CFG produces $a^*bbb...ccc...d^*$ (equal number of b,...
1
vote
1answer
377 views

Proof that the grammar is LL(2)

I am given the following grammar: $ S \rightarrow AabAba \\ A \rightarrow a | \epsilon $ and I have to prove it is LL(2). I know what LL(k) means - one can choose a production based on k characters ...
1
vote
2answers
62 views

Why can't exhaustive search parsing stop after |w| + 1 derivations?

If my grammar does not have productions of the form $A\rightarrow\lambda$ and $A\rightarrow B$ for some variables $A$ and $B$ then I know that each step in the derivation must involve an increase in ...
2
votes
1answer
164 views

How to prove prove $L(G) = \{~w\in\{a,b\}^*~|~\#_aw= \#_bw\}$ for my CFG $G$?

For language $L = \{ x \in \{a,b\}^* \mid \#_a x = \#_b x \}$, I came up with the following CFG: $$S \rightarrow aSbS \mid bSaS \mid \varepsilon.$$ It can be easily shown that it is correct (quick ...
0
votes
1answer
52 views

Context-Free Grammar from this language

I'm having difficulties with an exercise in a theoretical CS class. The problem is: let $L_{2}$ be a language defined as follows: after every "a" come atleast two "b" or after every "b" comes atleast ...
-1
votes
1answer
216 views

Convert grammar to Greibach form

The grammar is $S \rightarrow AA|a$$A \rightarrow SA|ab$The actual question is to find an NPDA accepting the language generated by this grammar but for that i firstly need to convert it into Greibach ...
1
vote
1answer
236 views

CFG - Ambiguous to Unambiguous

Given the ambiguous CFG : S → 01S1|SS|ϵ I came up with the following CFG which I think is unambiguous: S → 01X | 011X X → 01X1 | ϵ Is my CFG unambiguous and does it represent the same language?
3
votes
2answers
1k views

CFG for language of all palindromes whose number of 1s is divisible by 3

The question is the following: Construct a CFG for $L_2 = \{w \in \{0, 1\}^* \mid w = w^R\text{ and the number of 1’s in $w$ is divisible by 3}\}$. I can construct a CFG for $\{w \in \{0,1\}^* \...
0
votes
1answer
39 views

What's wrong with this grammar

$L = \{ w : w \in \{a, b\}^* \land |w|_a = |w|_b\}$ where $|w|_a$ means number of $a$ in string $w$. I came up with this grammar: $S \rightarrow aSb \ |\ bSa \ | \ \epsilon .$ Can someone please ...
3
votes
0answers
101 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
1answer
173 views

Find a regular grammar that generates words with even number of a's

I have a language $L$ = {$vabu$ | $v$,$u\in \{a,b\}^*$, $|vu|_a = 0$ $($mod $2)$$\}$ where $|vu|_a$ is number of $a$ in $vu$. I came up with these rules: $\sigma \rightarrow aa\sigma | ab\xi$ $\...
2
votes
3answers
82 views

Given an CFG determine if $\varepsilon \in L(G)$

Given a context free grammar how am I able to determine if $\varepsilon \in L(G)$ ? The only way I thought of is to systematically check if I can derive the empty word from the given grammar. (...
1
vote
1answer
298 views

Is the problem of determining whether a CFG generates a string in the form 0*1* decidable?

Given a grammar $G$, is it decidable whether $G$ generates any string in the form $0^*1^*$? Why? I think it's undecidable but can't find any undecidable problem to reduce it to.
1
vote
3answers
266 views

What is a non-ambiguous CFG for generating the set of natural numbers?

I'm trying to write a non-ambiguous context-free grammar that can generate the set of natural numbers, including the 0. My current solution is the following grammar: $\mathcal{G}: S \rightarrow 0\ |\ ...
3
votes
1answer
80 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) &...
1
vote
0answers
45 views

Grammar for invertible functions

Has anyone ever come up with a grammar that only induces invertible functions, and does so in a way where it is possible to algorithmically construct the inverse function? It could be useful for ...
1
vote
1answer
38 views

Words generated by CFG whose parse tree contain even number of $X$

Let $G$ be a context-free grammar with set of terminals $A$. Let $X$ be a non-terminal in $G$. Is the language of words over the alphabet $A$ with a syntax tree in which the non-terminal $X$ appears ...
2
votes
1answer
296 views

Context formal language recognizing even number of 0's and odd number of 1's

I have an assignment, it's asked to write a context free grammar recognising the language $L=\{ w \mid w\text{ has an even number of }0\text{s and an odd number of }1\text{s}\}$, over the alphabet $\{...
1
vote
1answer
102 views

How to transform lambda function to multi-argument lambda function and how to rewrite or approximate terms?

I am trying to do the formal semantics (Montague grammar, abstract categorial grammar) of natural language and encode the sentence John is boss. The type system has ...
1
vote
1answer
156 views

Using a context free grammar to generate sample utterances for Amazon Alexa/Google Assistant?

I would like to get some opinions about using a context free grammar to generate sample utterances for Amazon Alexa/Google Assistant skills. When developing these skills one has to provide a large ...
2
votes
1answer
413 views

What is handle in bottom up LR parsing?

I was taking course on compilers by Alex Aiken. You can find the slide discussing handles on this page. On the page of the slide, the instructor defines handle as follows: Assume a rightmost ...
0
votes
1answer
71 views

Define a grammar to emmulate chess rules

Is it possible to define a 《chess language》: language={alphabet = {(chess pieces, squares of chess board)}, grammar={rules of movement of pieces over the board}}? I looked online but I cannot find a ...
1
vote
1answer
93 views

Formal grammar with variables for consistent substitutions

In a rewriting system, suppose the production rule S→xAyAz (or <S>:=x<A>y<A>z, in BNF), where S and A are ...
2
votes
0answers
36 views

Intuition on what an attribute grammar can achieve

I have seen attribute grammars for a small handful of tasks: Parsing simple arithmetical expressions Type checking Checking that a variable is initialized anbncn (seems to be a favorite toy example).....
1
vote
1answer
130 views

Why I can't parse factorial? [closed]

Given that I have a simplified Bison BNF grammar: ...
0
votes
1answer
487 views

Context-free grammar for $L=\{0^n1^{2n} \mid n \geq 0\}$ [closed]

How can I express this language $L = \{0^n 1^{2n} \mid n ≥ 0\}$ as a context-free grammar? I am new to this field and I am not sure what should I do. Please help me.
0
votes
1answer
135 views

Different context-free grammars for the same language

In context-free grammar, are both the following grammars correct for the same language? $$L = \{a^mb^n : m, n \in N_0 \text{ and } m \ne n\}$$ (grammar one) $S \to S_1 | S_2$ $S_1 \to A_1B_1$ $...
0
votes
1answer
56 views

Can you automatically generate a parser for a type using type theory some how?

Was wondering since all the types are spelled out constructively, and the constructions can all be reflected symbolically on a computer, if you can automatically parse expressions in a type?
1
vote
1answer
117 views

Right definition of linear grammar

I was referring book by Peter Linz, which defines linear grammar as follows: A linear grammar is a grammar in which at most one variable can occur on the right side of any production, without ...
0
votes
0answers
78 views

Is a Turing Machine able to reduce a grammar by chomsky hierarchy? [duplicate]

If given a grammar, for example, a context-sensitive (type 1) can it always be "reduced" to a equivalent context-free grammar (type 2) and so on for grammars type 2 to "reducing" and getting a type 3? ...
1
vote
1answer
79 views

Is it possible for a Turing machine to be able to reduce a grammar and tell where it fits in chomsky hierarchy?

For example: This looks like a context free grammar: 𝑆 → 𝑄𝑅𝑇 𝑄 → 𝑎𝑄 | 𝑎 𝑅 → 𝑏𝑅 | 𝑏 𝑇 → 𝑐𝑇 | c but it can be reduced to this regular language: 𝑆 → 𝑎𝑆 | 𝑎𝑅 𝑅 → 𝑏𝑅 | 𝑏𝑇 𝑇 → 𝑐𝑇...
1
vote
1answer
443 views

Parse Trees and Operator Precedence

I have the following basic BNF grammar: ...
0
votes
0answers
162 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
79 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
1k 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
615 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
53 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
272 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
581 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
85 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
450 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
104 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
91 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
149 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
80 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
3 4
5
6 7
20