Questions tagged [formal-grammars]

Questions about formal grammars, generative descriptions of formal languages.

Filter by
Sorted by
Tagged with
0
votes
0answers
40 views

Given a CFG and one of its nonterminals $v$ determine if there exists a sentential form beginning with $v$?

I am supposed to find an algorithm solving the following problem: Given a CFG $\;G=(V_N, V_T, R, S)$ and a nonterminal $v \in V_N$ determine if there exists a sentential form which begins with $v$. ...
0
votes
0answers
9 views

Writing a Grammar to a Language [duplicate]

is there a general method or approach to writing grammars to a language? I do not want to describe the language I have to write a grammar to as I do not want a specific answer. I am looking for ...
0
votes
0answers
15 views

What complexity class does is this set of grammars? L-complete?

Given a grammar where every rule has the form $X \to Y$ or $X \to a$ and (($X \to Y$) implies ($Y \to X$)) where $X,Y$ range over nonterminals and $a$ ranges over terminals, and given a nonterminal $S$...
0
votes
1answer
38 views

Grammars and Parsing: Ambiguity in Sequences

BACKGROUND I am writing a grammar and parser for a domain-specific language. There is a specific form of expression that, while simple, is giving me headaches. Given terminals: "a": KEYWORD "b": ...
0
votes
0answers
19 views

Grammar for $\{a^n b^m c^{n+m} \mid n,m \ge 1\}$ [duplicate]

Please help me solve this problem: Design a grammar for the language $\{ a^n b^m c^{n+m} \mid n,m\ge 1\}$.
0
votes
1answer
21 views

Build LL(1) parsing table for grammar S -> iSeS | iS | a

Task Bulid parsing table for grammar S -> iSeS | iS | a Resolve conflicts in this table and simulate parser work for word ...
0
votes
1answer
29 views

Determining recursive enumerability of given languages

I came across following problem: $L=\{M$ is a turing machine $M$ accepts two strings of different length $\}$ $L=\{M$ is a turing machine $M$ accepts atleast two strings of different length $\}...
0
votes
0answers
26 views

How to include both precedence and associativity in following grammar?

For the following grammar, how can I include both precedence and associativity of operators: S -> S|S S -> S.S S -> S* S -> (S) S -> a|b Note: In the first rule ...
0
votes
0answers
22 views

Find equivalent LL(1) grammar

There is sample question to calculate equivalent LL(1) grammar for below grammar: $S \rightarrow S b$ $S \rightarrow S d$ $S \rightarrow c S$ $S \rightarrow c c a$ At first step, ...
0
votes
0answers
23 views

Dangling Else Ambiguous Grammar

How is the following grammar ambiguous stmt -> if expr then stmt | matched_stmt matched_stmt -> if expr then matched_stmt else stmt | terminal
0
votes
0answers
30 views

Is this correct transformation of a grammar to one without left recursion?

So the last few days I am writing a compiler for a subset of C language by given grammar for a class at university. I encountered this problem and then I realized I need to remove left-recursion in my ...
0
votes
1answer
73 views

What does {a,b}* for DFA's mean?

For instance when the question contains $\{a,b\}^*$ does this mean that the DFA must have at least one $a$ and one $b$ on top of whatever conditions it has? For example a DFA that accepts $\{w \in \{a,...
0
votes
0answers
11 views

Detect a class of a grammar having its DSL AST

I have a grammar for some language written in some DSL for writing grammars, and this DSL implements EBNF. I have an AST for the description of a grammar in the DSL. How can I detect the minimal class ...
0
votes
1answer
35 views

Is this grammar LL(1) grammar?

Is this grammar LL(1)? Would it be a problem that S can be both E/S and E? S -> E / S S -> E E -> letter E -> ‘ S ’ Can it derive ‘a / e / ‘g / s’ ’...
0
votes
0answers
58 views

I´m having problems with this Context Free Grammar

I am not able to convert the following language to a Context Free Grammar. The major problem is how to pump both "sides" of the word to obtain same number of 0s and 1s, but, without creating a series ...
0
votes
1answer
18 views

Ambiguous Grammar demostration exercise

Hi im stuck on an exercise of ambiguous grammar. I need an example that shows that this grammar is ambiguous. The grammar is defined as follows: $$S \rightarrow aT | bR$$ $$R \rightarrow a | aS | bRR$...
0
votes
1answer
243 views

Convert ambiguous grammar to unambiguous and SLR(1)

I have the following ambiguous operator grammar: E->E+E*E | E-E*E E->E+E | E-E | E+E | E*E | E/E E->(E) | x I must convert it to an unambiguous one ...
0
votes
0answers
144 views

Grammar for language L on {a, b} where L = {w|na(w)mod 3 = 0} [duplicate]

I am able to form the regular expression but I am not confident with the grammar. I have tried the following: S-->aaaS|bS|b|lambda Regular expression is given by: ...
0
votes
1answer
149 views

How to convert the left recursive grammar into right recursive grammar

I have a grammar: $A\rightarrow Aa|bB|c$ The above is the left recursive grammar. I understand that I have to remove the string "Aa" from the above grammar or to convert it into the form "aA" to ...
0
votes
0answers
43 views

Converting from cfg to cnf (Chomsky normal form)

I am trying to convert this grammar from context free grammar with kleene star productions into the Chomsky normal form equivalent. I am having a hard time trying to understand how to do this, I need ...
0
votes
0answers
30 views

Are these two things parsing a sentence and solving a problem in a turing machine equivalent?

I'm an undergrad currently studying Advanced Topics in Algorithms, Compiler Techniques, and Natural Language Processing. I'm wondering whether these two things are equivalent. Given a sentence and a ...
0
votes
0answers
28 views

Use the pumping lemma for context free languages to prove L = {w#w | w \in {a,b}*} is not context free

I know the basics of using the pumping lemma for CFG to prove a language L is not context-free, however, the # symbol seems to be throwing me off or my understanding is not complete.
0
votes
0answers
26 views

question about LL(1) and LR(0)

If grammar is an $LL(1)$ and does not contain any null production (i.e $V \rightarrow \epsilon$) then does that grammar necessarily be an $LR(0)$ grammar? I have tried to find counterexample for ...
0
votes
1answer
152 views

How to determine valid handle for given bottom up parser?

I came across following question: Consider the grammar: $E → E + n\text{ | }E × n\text{ | }n$ For a sentence n + n × n, the handles in the right-sentential form of the reduction are (...
0
votes
0answers
66 views

How to find a context-free grammar from a difficult language? [duplicate]

Some Languages are trivial to find their respective context-free grammar. Like for example $ L= \{a^nb^n: n \geqslant 0\}$. However some are really difficult to solve. I would like to have some advice ...
0
votes
0answers
34 views

Formal definition for strong equivalence of grammars/parse trees

The Wikipedia article on equivalence of formal grammars defines weak and strong equivalence as follows: In formal language theory, weak equivalence of two grammars means they generate the same set ...
0
votes
0answers
73 views

Conversion of left-recursive context-free grammars to strongly equivalent ones without left-recursion

It is a well-known problem that many top-down parsers have problems parsing a context-free grammar with left recursive rules. There exist algorithms to convert grammars with direct or indirect left-...
0
votes
0answers
128 views

Is Python's Grammar in a known Category between CFG and CSG?

I have a high level understanding of formal languages and grammars, and I'm familiar with the four major types of grammars in Chomsky hierarchy. I was interested in knowing the classification of ...
0
votes
0answers
66 views

Whether following language is linear or not?

I have a language $L= \{a^nb^nc^m : n, m \ge 0\}$. Now, I wanted to determine whether this language is linear or not. So, I came up with this grammar: $S \rightarrow A\thinspace|\thinspace Sc$ $A \...
0
votes
0answers
23 views

Why are CFL not closed under set difference, and complementation? [duplicate]

I was wondering why CFL are not closed under set difference, and complementation can anyone explain? I tried searching, but no luck.
0
votes
0answers
26 views

Is $LR(k) \subset SLR(k+1)$ for $k=1,2,…$? [duplicate]

I know that: Point 1: Set of languages accepted by $LR(0)$ parsers $\subset$ Set of languages accepted by $SLR(1)$ parsers Does this logic hold for higher $k$'s? That is, does following fact hold?...
0
votes
0answers
56 views

Creating a grammar for a a language for instructions, with repititions

I have a language that consists of instructions for movement on a 2D-plane. You start at coordinate [0,0] The instructions DOWN 1 UP 10 LEFT 5 RIGHT 1 means you ...
0
votes
0answers
45 views

Is there any grammar parseable by LALR(1) but not LR(1)?

https://en.wikipedia.org/wiki/LALR_parser - as far as I understand, LALR(1) is a simplified version of LR(1), aiming to achieve a greater parsing performance at the expense of reduced power. So, IIUC, ...
0
votes
2answers
66 views

Regular grammar with at most one c

I am attempting to make a regular grammar over alphabet {a, b, c} where there is at most one c. So far, I have the regular expression ((a|b)*|c)(a|b)* but am unsure ...
0
votes
0answers
98 views

How to check if a string is accepted by a context-sensitive grammar?

Is there an algorithm to determine membership in context-sensitive grammars?
0
votes
0answers
168 views

The rightmost derivation is possible with the same rule of leftmost derivation

Can someone please help me in understanding the statement. What does it exactly mean? What I think it means is that: the derivation produces by the leftmost derivation is also possible with rightmost ...
0
votes
0answers
56 views

Grammar for context free language

I want to give a grammar for the following language: $$L = \{x^r \# y |x, y \in \{a, b, c\}^*\\ \text{ and }x\text{ is a contiguous sub-string of }y\}$$ where $x ^ r$ denotes the backward written ...
0
votes
0answers
79 views

Difference between grammar productions and derivations

My understanding is that a production is a 'rule' of a grammar which defines how a symbol sequence can be rewritten into another symbol sequence. A derivation on the other hand is the process of ...
0
votes
0answers
58 views

What is “Phrase structure grammar”?

I'm undertaking Theory of Computation Classes. I came across this sentence while studying Recursively Enumerable Grammar: Type-0 grammars generate recursively enumerable languages. The ...
0
votes
1answer
29 views

How to generate a grammer from this language? [duplicate]

I'm trying to generate a grammar from this language: L={a^i b^j c^k d^l : i+j=k+l} to be clear its a in the power of i and b in the power of j... and so on, so ...
0
votes
1answer
86 views

Ambiguous grammar to equivalent unambiguous grammar

I stumbled on this ambiguous grammar and I've been trying to make it unambiguous but it's still ambiguous. Given the ambiguous CFG : $S \to A\mid B$ $A \to aAb\mid ab$ $B \to abB\mid \epsilon$ My ...
0
votes
0answers
22 views

Are there any formal grammars describing the set of all directed graphs?

Let GRAPHS be the set of all directed graphs. Is there a set of strings STRYNGS such that there exists a bijection ...
0
votes
0answers
69 views

How a regular language , context free language and context sensitive grammar are used in compilers to shape up the languge? [duplicate]

I know that regular language can be used for pattern matching , context free language is used for syntax matching and context sensitive for semantic or meaning of the sentence . But i have found it ...
0
votes
1answer
22 views

Grammar with same variables

If a grammar has the same variable multiple times, is it the same as adding a $\mid$ between them? For example, is $$\begin{align*}S &\to bB \\ S &\to \varepsilon \\ B &\to cB \\ B &...
0
votes
1answer
340 views

Handling epsilon productions in recursive descent parsing

I am working on a recursive descent parser for lambda calculus. In my grammar, after removing left-recursion, I am left with the following two productions: ...
0
votes
1answer
105 views

Is this a correct grammar for untyped lambda calculus?

I am trying to write a recursive-descent parser for untyped lambda calculus. While researching the way of formulating the grammar, I managed to put together something like this: ...
0
votes
1answer
71 views

Reusing variable in converting grammar to Chomsky Normal Form

I'm not sure if reusing variable is allowed in CNF. For example, I have this grammar not in CNF. So I have to convert it to CNF. ...
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 ...
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 ...
0
votes
1answer
654 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.