Questions about formal grammars, generative descriptions of formal languages.

learn more… | top users | synonyms (1)

0
votes
0answers
9 views

Show that language generated by grammar is regular [duplicate]

We have grammar with nonterminals $ X_1,...X_n$ terminals $V_t$ and rewriting rules of form: $X_i \rightarrow a \in V_t $ $X_i \rightarrow X_jX_k, \ i \ge j , \ i > k $ How can I show that ...
2
votes
1answer
26 views

Explanation of Grammar Ambiguity

Consider now the grammar G S -> (S + S) S -> (S * S) S -> a Is it ambiguous? Answer: No because there are disambiguating parentheses and so no left or right recursion. Can someone explain how the ...
0
votes
3answers
73 views

What is the language generated by a given grammar

Given the grammar $s \to aSb \mid bSb \mid a \mid b$; what is the language generated by the grammar over the alphabet $\{a,b\}$? When I was solving this question I was a bit confused about ...
-2
votes
1answer
24 views

CFG for the language “number of a's = number of b's + 2”

How can I construct a context-free grammar for the following language? $$ L = \{ w \in \{a,b\}^* : \#_a(w) = \#_b(w) + 2 \}. $$ Please help me out in this. I am not sure how to approach this ...
1
vote
2answers
53 views

Show that a language cannot be generated by linear grammar

I have a language $ L= \{ w \in \{a,b\}^* ; |w|_b=2i, i \ge 0 \}$ that is a language with even number of b's. I found a grammar for it with these rules: $S \rightarrow aS \ | \ bL \ | \ \lambda ...
3
votes
2answers
42 views

Meta-grammar for context-free grammars

Formal grammars like regular expressions (REs) or context-free grammars (CFGs) specify languages, i.e. sets of strings over an alphabet. Grammars themselves can be seen as languages, e.g. the set of ...
-1
votes
1answer
35 views

Could someone please explain this language to me and its grammar? [closed]

This is the problem: http://i.imgur.com/Io7h1en.png This was a problem I saw and I really have 0 clue what the Language means the (**) part, and its solution. I was wondering if anyone could please ...
-3
votes
0answers
23 views

What is the language of the following grammar?

Let be $G_3= (\{B,S,M,X,Y\},\{a,b\}, P_3,S)$ with $$\begin{aligned}P_3=\{&S\to XMY \mid XY,\\ &M\to aM\mid BM\mid a\mid B,\\ & Bb\to bB,\\ & Ba\to aB,\\& BY\to bY,\\& Y\to ...
-4
votes
2answers
60 views

odd length palindrome's f=language [closed]

Find the language generated by the following grammar over the input alphabet = {a,b}. S –> aSa | bSb | a | b The language generated by the above grammar over the alphabet {a,b} is the set of (A) ...
3
votes
1answer
61 views

Need for an augmented grammar

The question is under the concept of LR parser. Suppose the original grammar is S->AA A->aA|b Is it necessary to add an additional rule S'->S to make it as augmented grammar? In short, I want to ...
0
votes
0answers
30 views

Proof of completeness for CFG having twice as many zeroes as ones [duplicate]

One possible CFG containing twice as many zeros as ones can be, S -> 0S0S1S | 0S1S0S | 1S0S0S | ϵ (This CFG is redundant but it will do the job. So I am not interested in the redundancy. Other ...
0
votes
1answer
25 views

How to choose symbols to replace for this left-most derivation?

I have a context free grammar such as the following: $E→E+T | T$ $T→T×F | F$ $F→(E) | a$ Using the left-most derivation, the following can be derived: $E⇒E+T⇒T+T⇒F+T⇒a+T$ $⇒a+F⇒a+(E)⇒a+(T)$ ...
1
vote
1answer
33 views

Why do we not use CFGs to describe the structure of lexical tokens?

This was an exam question for my course and I am struggling to actually answer it in a way that is not fluff. Here is my current answer: CFGs describe how non-terminal symbols are converted into ...
0
votes
1answer
36 views

Context free grammar for nested arrays separated by commas

I have to define a context free grammar for the following rules: (i) A pair of square bracket tokens [] surrounding zero or more values separated by commas. (ii) A value can be another array or a ...
1
vote
2answers
53 views

non LL(1) grammar but LL(1) language

I'm reading a Basics of Compiler Design and on page 84 it is making the following statement: A language may well be LL(1) even though the grammar used to describe it is not. Can someone give ...
0
votes
1answer
22 views

Is the given grammar LALR

We are given the following grammar. S-->AS/b A-->SA/a We have to tell if its LALR or not. As we all know that LALR is only minimization of CLR, So first I constructed the CLR parsing table using ...
4
votes
1answer
55 views

Is it decidable whether a linear language contains a square?

A square is a word of the form $ww$. A linear grammar is a CFG that has productions of the form $A\to uBv$ or $A\to u$ (with lower case symbols corresponding to terminal strings). Question: Is it ...
3
votes
0answers
53 views

Context-free grammar for DAGs?

I'm looking for a "safe" representation of DAGs. With "safe" representation I mean that it can be described by a context-free grammar. Ideally, this grammar would be suitable for a simple LR parser. ...
0
votes
0answers
13 views

why the end marker is part of a follow set of a start symbol?

I can't figure out why the end marker is part of the follow set of the start symbol, in other words if $\$$ is the input-end marker and $S$ is the start symbol then $ \$ \in Follow(S)$. My question is ...
4
votes
3answers
273 views

Is the set of CFGs that contain all odd and even length words Turing-decidable?

$ALLEVEN_{CFG}$ = {M is a grammar, and L(M) includes all strings of even length in $\Sigma^*$} = {(M): ($\Sigma\Sigma$)* ⊆ L(M)} $ALLODD_{CFG}$ = {M is a grammar, and L(M) includes all strings of odd ...
0
votes
2answers
19 views

Different between Left most and Right most derivation [duplicate]

I am a beginner started learning theoretical computer science.. I just came through. "Context free grammar" So my Question is that what is the different between Left most and Right most derivation. ...
-2
votes
2answers
90 views

Why do grammars in Chomsky Normal Form have derivations of length 2n-1?

I would like to know how they obtained the expression $2n-1$ as said from the excerpt of article (p.3): The key advantage is that in Chomsky Normal Form, every derivation of a string of n letters ...
-1
votes
2answers
49 views

Design a grammar for this context-free language

I am doing an exercise from Models Of Computation - Ch - 5, Q-1(r). Design a grammar that generates this context-free language $\{ x\space\$\space y^R \,|\, x, y \in\{0, 1\}^* \text{ and } x \ne ...
0
votes
1answer
40 views

Converting context-free grammar to Chomsky/Greibach Normal Form

Is it necessary to remove all lambda productions, unit productions and useless productions from a context free grammar(CFG) before converting to Chomsky Normal Form(CNF) or Greibach normal form (GNF). ...
5
votes
2answers
657 views

In context-free grammar (CFG), what is the importance of doing both leftmost and rightmost derivations?

I am a beginner learning theoretical computer science. While learning about CFG, I found that doing both leftmost and rightmost derivations gave me the same parse tree. So, my question is: Why is it ...
0
votes
1answer
36 views

Need to remove indirect left recursion from CFG

I need to remove indirect left recursion from the following CFG: remove indirect left recursion from the following CFG. $$A → Ba| b$$ $$B → Cd | e$$ $$C → Df | g$$ $$D → Df | Aa | Cg$$ In the ...
1
vote
1answer
31 views

How do I get and/or verify a formal Grammar for a given formal Language? [duplicate]

I was given the Language $L=\left \{ a^nb^na^nb^n |n\epsilon \mathbb{N} \right \}$ and I'm supposed to find a Grammar that generates that Language. After some trying and fiddling I found one that I ...
0
votes
0answers
21 views

Parsing text in two dimensions

I would like to define grammar rules which define how a token is related not only to the left and to the right (as in usual stream of characters that parses deal with), but also to the top and to the ...
0
votes
1answer
28 views

Writing context free grammar

I have the following language: {0m1n0n1m | m,n ≠ 0} I was wanting to write Context-free grammar for it. I'm a little confused because the rule doesn't mention that m and n are not equal to each ...
1
vote
0answers
25 views

Modifying the grammar to include another operator

I have this grammar for arithmetic expressions E -> E+T | T T -> T X F | F (X is cross product operator) F -> (E) | a Now I am wanting to add the exponential operator ^ to it, it needs to ...
1
vote
1answer
42 views

Proof that the set of all universal CFGs is co-RE complete

Let $\Sigma^*\text{CFL} = \{G \mid G \text{ is a CFG; } L(G) = \Sigma_G^*\}$. Enumerate the r.e. sets by $W_n$. Let $\text{EMPTY}= \{ n \mid W_n=\emptyset\}$. On page 4 of these lecture notes, to ...
0
votes
2answers
85 views

Grammar for square numbers in unary

I have to write a grammar for the following language: $$\{1^{n^2} \mid n\geq 1 \}$$ I am having trouble figuring out the production rules. I was thinking of using the fact that $n^2$ can be written as ...
3
votes
1answer
63 views

Can I remove left recursion on this grammar

$S \rightarrow Sa \mid S \mid \epsilon$ This is a weird case where I have only one non-terminal. I'm trying to apply the algorithm 4.19 in the dragon book. It don't think it should be applicable but ...
-2
votes
1answer
63 views

Context sensitive grammar for an odd number of copies of the same word

Let $L = \{ w^m \mid m = 2k +1, k \ge 1 \}$. Please give some idea to write a Context sensitive grammar for $L$. Will it be like $L' = \{www \mid w \in \{a, b\}^*$? Then for each $w$ we have to ...
2
votes
1answer
33 views

What is examples of languages to prove the inclusions between families of languages generated by matrix grammars?

$\lambda M_{ac}$ = family of languages generated by matrix grammar with appearance checking and with erasing rules $\lambda M$ = family of languages generated by matrix grammar without appearance ...
2
votes
1answer
32 views

Not respecting the 3rd rule of a LL(1) grammar

I'm trying to build a grammar that violate only the 3rd rule. I'm trying to figure out what kind of grammar would not respect that. I think the grammar has to be left-recursive to not respect it. if ...
0
votes
1answer
69 views

How to write an EBNF grammar for Java float literals?

I've got this question on my study guide: "Write an EBNF grammar description for Java float literals and one for Java double literals." I've browsed the Oracle site and found the grammar for java ...
7
votes
5answers
616 views

Is there a known method for constructing a grammar given a finite set of finite strings?

From my reading it seems that most grammars are concerned with generating an infinite number of strings. What if you worked the other way around? If given n strings of m length, it should be possible ...
1
vote
1answer
48 views

Regular languages and constructing a regular grammar

I'm pretty new to computer science and just read about the concept of grammars. Now, I have a practical problem to solve. Here is the alphabet {a, b, c, d}. How ...
1
vote
0answers
19 views

Let $L=\{a^nb^nc^n | n\geq 0\}$ , then $\overline{L}$ is context free [duplicate]

I need help with this problem. I proved that $L$ is not context free (using Ogden's lemma), but I can't prove that $\overline{L}$ is context free. I'm thinking about a proof by cases (if $\#(a)=\#(b) ...
4
votes
1answer
19 views

How to make sense of this context-sensitive production in a textbook? (a typo perhaps?)

In Chapter 1 of Kenneth Slonneger and Barry L. Kurtz's Formal Syntax and Semantics of Programming Languages: A Laboratory Based Approach, an example of its production is given to illustrate the nature ...
2
votes
1answer
32 views

CFG for words that are not a concatenation of the same word [duplicate]

I am teaching myself formal languages, and yesterday i got stuck at an exercise asking for a context free grammar for the language: $ L = \{x \in \Sigma ^{+} | \ \forall w \in \Sigma ^{+} \ x \neq ...
1
vote
1answer
87 views

Calculi for a computability class

Proving two push down automata equivalent is undecidable. But proving two finite state machines equivalent is decidable. You also cannot write a programming language that allows expressing the ...
1
vote
1answer
28 views

Indirect Left recursion

I'm solving (indirect Left Recursion) for these production rules . S is the starting symbol. S -> Aa / a eq1 A -> Sb / b. eq2 Now I can do this in two ...
0
votes
1answer
41 views

Grammar ambiguous or not?

So I've been struggling for the past hour with $G=(\{S\},\{a,b\},P,S)$ with productions $S\to aaSb | abSbS | \varepsilon$. I need to prove whether this grammar is ambiguous or not. Thus far I think it ...
1
vote
1answer
47 views

Equivalence of regular grammars

I know that proving context free grammars equivalent is undecidable. I also know that proving if a context free grammar recognizes a regular language is undecidable. Here is my question: is proving ...
1
vote
0answers
47 views

How to find conflicts in LALR parser?

I have a LR analyser and I can't find out how to know whether the grammar is or is not LALR(1). I think that I have to merge states with the same rules. So I have to merge states: $2 - 12, 3 - 13, 4 ...
3
votes
2answers
76 views

Is it decidable whether a given context free grammar generates an infinite number of strings?

Is the decision problem "Does a given context free grammar generate an infinite number of strings" decidable? In order to test whether a context free grammar generates an infinite number of strings or ...
3
votes
1answer
260 views

How can I check that the language of one context-free grammar is a subset of a second context-free grammar?

Could you explain me, how can I check, that the language of first context-free grammar (G1) is a subset of the language of second context-free grammar (G2). G1 and G2 are two LL(1) grammars with ...
0
votes
1answer
52 views

How do I derive a regular grammars from this regular expression? [closed]

How do I derive a regular grammars from this regular expression? (a or b)*ba(ba)* I'm stuck with the last part so ...