Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions about formal grammars, generative descriptions of formal languages.

2
votes
1answer
62 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
21 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
30 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
42 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
77 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
33 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 ...
1
vote
1answer
33 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
46 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
49 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 ...
0
votes
0answers
23 views

Chomsky Normal Form (Removing Unit Production)

Remove unit and null productions... $$ \begin{align} S &\rightarrow Ua \\ U &\rightarrow aUbb\mid S\mid \epsilon \end{align} $$ Removing null production ($U \rightarrow \epsilon$) first ...
2
votes
0answers
18 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
79 views

Why I can't parse factorial? [closed]

Given that I have a simplified Bison BNF grammar: ...
0
votes
1answer
36 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
36 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
50 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
29 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
13 views

Equivalent grammar in Chomsky Hierarchy [duplicate]

I want to know 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 ...
0
votes
0answers
57 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? ...
0
votes
1answer
43 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: 𝑆 → 𝑎𝑆 | 𝑎𝑅 𝑅 → 𝑏𝑅 | 𝑏𝑇 𝑇 → 𝑐𝑇...
0
votes
0answers
13 views

What production rules produce propositional logic tautologies?

Production rules correspond to Turing machines: [U]nrestricted grammar[s]...can generate arbitrary recursively enumerable languages. There is a Turing machine that can recognize tautologies in ...
1
vote
1answer
43 views

Parse Trees and Operator Precedence

I have the following basic BNF grammar: ...
0
votes
0answers
28 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
150 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 ...
0
votes
0answers
19 views

How many sets of LR(0) items exist in this grammar? (question from the dragon book)

The grammar: \begin{align} S&\rightarrow A_ib_i &\text{for }1\le i\le n\\ A_i&\rightarrow a_jA_i\mid a_j &\text{for }1\le i,j\le n\text{ and } i\neq j \end{align} The answer is $2^n +...
1
vote
1answer
50 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
0answers
19 views

Transform grammar into LL(1) left-associative

I was looking on some old exam questions for a course in my university, and stumbled upon an exercise that asked for the following: The starting grammar was this: ...
0
votes
1answer
27 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
94 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
24 views

How to convert LL to RR grammar?

I need to convert the LL grammar to LR? I am a noobie in this question. I found an algorithm to remove a left recursion but I'm not sure it will convert it in the RR grammar... Can anyone advice ...
0
votes
0answers
28 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
46 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
178 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
36 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)...
0
votes
0answers
12 views

How to convert this CFL into a CFG? [duplicate]

I'm trying to convert the following context free language into a context free grammar. $L = \{a^i b^j c^k \,|\, i+2j=4k;\, i, j, k ≥ 0\}$ I am struggling given the fact there is a large number of ...
3
votes
2answers
83 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 ...
0
votes
0answers
33 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 ...
4
votes
1answer
36 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
17 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
96 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
30 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
26 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
38 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
72 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 &\...
0
votes
0answers
26 views

How can i define left-recursions?

I'm new with parsing and I already understood (finally) how I can go from A -> Bxy | x B -> CD C -> A | c D -> d to ...
1
vote
1answer
50 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
0answers
22 views

Value of k for the LL grammar?

For the language, a^n b^m c^n+m and the grammar \begin{align*} S&\to aAc \\\ A &\to aAc \mid bBc\\ B &\to bBc \mid \lambda \end{align*} What would the value of k be since this is an LL(k)...
0
votes
1answer
37 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
23 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
30 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
63 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 $ = ...