Questions about formal grammars, generative descriptions of formal languages.

learn more… | top users | synonyms (1)

-1
votes
0answers
22 views

How to convert a context free grammar to a left linear grammer

Can anyone tell me whether the following grammar is LL(1) or not if not can you please suggest how to convert it into LL(1)? To the best of my knowledge it is not LL(1) because ...
-1
votes
0answers
8 views

Very basic example question on FOLLOW sets, need some clarification

I highlighted the part I don't understand in red. Basically, where did the 'd' come from (second red line)? I thought FOLLOW(SB) is just $.
-1
votes
1answer
49 views

Some Algorithm on Decidablitly [on hold]

Anyone could correct me that Why just (1) is False. i'm not sure why others are true: ( G is a Context Free Grammar). any brief description? There is an algorithm that decides whether the ...
-3
votes
0answers
35 views

How to prove or disprove that the following is decidable [closed]

{<G,A> : G is a regular grammar and A is an unreachable variable in G} In a CFG G, a variable A is unreachable if there is no derivation S->*w with w ...
0
votes
2answers
25 views

Erasing $\epsilon$ production from CFG

I would like to delete the $\epsilon$-production from the context free grammar with the following rules P: $$S \rightarrow ASB , BSA, \epsilon$$ $$A \rightarrow aS$$ $$B \rightarrow bB, b$$ Now we ...
4
votes
1answer
29 views

Method for Creating Any Unambiguous Grammar?

I'm in an undergraduate class where we're studying formal grammars right now. I asked my teacher if there was any known set of rules for creating context free grammars that Was guaranteed to produce ...
2
votes
2answers
115 views

Can there be two different left most derevations for a grammar?

Suppose there is a CFG with the rules S--> Aa A--> Bb B--> A B--> Epsilon To my best understanding the left most derivation would go like this.. ...
0
votes
1answer
25 views

generating recursive descent parser

I have a grammar, $L \to A \langle A \rangle^*$ $A \to () \mid (L)$ but I am not sure how to generate parser for $\langle A \rangle$. I know in other case, for example, if $E \to T ...
2
votes
0answers
29 views

Removing hidden ambiguity in grammar using left factoring

I am trying to reduce the grammar to LL(1) for a hypothetical language we created. I have removed most of the left factoring issues in the grammar, using the general rule of introducing new ...
1
vote
1answer
31 views

Generate Regular Grammar for a Language with Modular Condition

This is a homework problem. I've wrestled with it for quite awhile and can't come up with a valid solution. The problem is: Find a regular grammar that generates each of the following languages: ...
-1
votes
0answers
10 views

What are the rules of a grammar producing a given language? [duplicate]

I'm trying to understand the logic on how to construct a grammar that produces a given language. For example, I found an unsolved exercise in my book and every time I create some rules I always find ...
2
votes
1answer
52 views

An example of a non-regular grammar for a regular language?

I understand that a regular language can be specified by either regular or non-regular grammars. What is an example of a non-regular grammar for a regular language?
1
vote
0answers
13 views

Referring to self publication in a monograph chapter [migrated]

I have a question regarding what tense form should I use to refer to an earlier self publication in a monograph chapter. For example, if I want to say (in the chapter), "most of the results were ...
1
vote
1answer
83 views

Relaxation of the null production restriction in Regular and Context Free Grammars

I am convinced of the fact that allowing productions of the form $S \rightarrow \epsilon$ in a context sensitive grammar would allow RE languages to be expressed if $S$ were on the right hand side of ...
1
vote
1answer
47 views

Is it Regular Language?

According to Wikipedia, Regular Language is Recognized by Some DFAs, or expressed by Regular Expression .. and all finite Language are regular but, not all regular is finite .. that's mean it may be ...
-1
votes
1answer
21 views

Programming Languages Grammar Ambiguity [closed]

I don't know if it is the right site to ask this. But we're studying about ambiguities of grammar. Including left most derivation and right most derivation. We are given the problem: ...
1
vote
1answer
37 views

Regular and not Regular Grammar

According the Peter Linz Book, am a confusing about the two example the Grammar G1 = ({S},{a,b},S,P1) with P1 given as S -> abS|a and G2 = ({S,S1,S2,},{a,b},S,P2) S -> S1ab S1 -> S1ab|S2 S2 -> a ...
0
votes
1answer
40 views

Regular Grammar and Regular Language [closed]

From Wikipedia, Regular Language All finite languages are regular. and Also Regular Grammar, is a way to describe the Regular Language Right regular grammar (also called right linear ...
0
votes
1answer
44 views

What context free grammar generates the language $L(G) = \{a^ib^jc^{2i}d^m\}$ [duplicate]

I am struggling to think of the context-free grammar that generates the language $L(G) = \{a^ib^jc^{2i}d^m\}$, where $i$, $j$ and $m$ are natural numbers. Also, in general, are there any good methods ...
-1
votes
2answers
82 views

Pushdown Automata: CFG to PDA

I have the following grammar for a context-free language: $G = (\{S,A,B\}, \{x,y,z\}, P, S)$ with $P = \{S \rightarrow A, A \rightarrow xAz, A \rightarrow xBz, B \rightarrow y\}$ My question is: How ...
0
votes
2answers
43 views

Computing FOLLOW sets for LL(1) grammar. Stuck on question

Calculate the FOLLOW sets for all the non terminals: $S \rightarrow bEx \mid Db \mid b \mid F$ $D \rightarrow EDc \mid Y$ $E \rightarrow dED \mid dDY$ $Y \rightarrow ab \mid ...
0
votes
1answer
36 views

Is this grammar LALR(1)

I am working through creating a LALR(1) parser generator. I have the following grammar which I designed to highlight the epsilon for rule 3. ...
1
vote
0answers
103 views

Is the complement of this language Context-Free $\{(a^nb^n)^m \mid n>0,m>0\}$?

I've been asked to decide whether a given language is a Context-Free Language (CFL). If yes, I should find the grammar that creates her, and if not, I need to prove it (with the pumping lemma). The ...
3
votes
0answers
19 views

Is there a grammar type for deterministic LBA?

Contextsensitive grammars define exactly the langauges acceptable by nondeterministic LBA. But how about deterministic LBA - is there a grammar type capturing exactly the languages acceptable by this ...
1
vote
2answers
45 views

How can this grammar parse such an input?

I've an example which I simply don't get at all. Implement an attributed grammar that checks that either the word ends in $b$ or each prefix of the word contains at least as many $b$s ...
-1
votes
1answer
39 views

Is this $LL(1)$ grammar valid?

Is the following a valid $LL(1)$ grammar: $ \begin{align} S &\rightarrow L \$ \\ L &\rightarrow M L_2 \\ L_2 &\rightarrow \underline{::} L \\ L_2 &\rightarrow \epsilon \\ M ...
0
votes
1answer
26 views

Let $L_4$ $\subseteq$ {0,1}$^*$ be the set of all palindromes whose first character is 1. Give a context-free grammar for $L_4$ [closed]

Let $L_4$ $\subseteq$ {0,1}$^*$ be the set of all palindromes whose first character is 1. Give a context-free grammar for $L_4$. I just wanted to check if my grammar is correct or not. $$A ...
0
votes
2answers
25 views

Relation between CLR Grammar and Ambiguity

I am studying CLR Parser and have a query about Grammar. If a Grammar can't be parsed using CLR(1) Parser ( i.e LR(1)) parser is it necessarily ambiguous? Is it possible that a grammar which is ...
4
votes
1answer
50 views

Do an ambiguous grammar and its corresponding unambiguous version generate the same language?

If I have an ambiguous grammar G and its disambiguated version D. Then which one is true L(D) ⊂ L(G) , L(G) ⊂ L(D) or L(G)=L(D)? As I tried with some examples to transform a grammar to it ...
1
vote
1answer
48 views

LALR(1) parsers and the epsilon transition

I am having trouble getting my head wrapped around epsilon transitions while creating an LALR(1) parse table. Here's a grammar that recognizes any number of 'a' followed by a 'b'. 'S' is an ...
0
votes
1answer
35 views

Help me find the ambiguity in this grammar

I've been sitting on this for 20+ minutes and can't seem to generate a string that is ambiguous. Can anyone help me? The grammar is: $$S \xrightarrow{} SS \mid T$$ $$T \xrightarrow{} aTb \mid ab $$ ...
2
votes
2answers
49 views

Context-free grammars and priority

This grammar is supposed to give priority to multiplication: E -> E + T | T. T -> T * F | F. F -> x. A derivation for "x + x * x" would be (unless I'm wrong): E => E + T => T + T => F + T => x + ...
2
votes
3answers
115 views

How to generate a context sensitive grammar

I am trying to solve for my exam coming up and have no clue how to generate the grammar for Context sensitive languages for example how do i proceed on this kind of question. Give a context-sensitive ...
0
votes
1answer
28 views

Is a grammar that accepts function declarations, function calls and expressions (at any order!) necessarily cyclic?

As the title suggests, assume a grammar which has to recognize function declarations, function calls, and expressions, at any order. Does that mean it has to be cyclic, and therefore ambiguous? I ...
3
votes
3answers
250 views

How to represent whitespace in a context-free grammar?

Say we want to support: xx The following grammar does accept it: S -> xAx A -> ε. because S => xAx => xx. But what about supporting: x x I realize this might be a stupid question but I'm ...
0
votes
0answers
45 views

Can we say we reduced a rule if we reduced an equivalent set of smaller rules?

I have constructed an SLR(1) parsing table with the following rules. S -> S + S + S (rule 1) S -> S + S (rule 2) S -> y Is reducing rule 2, then shifting + and y, then again rule 2, equivalent ...
-3
votes
1answer
27 views

Eliminating Null Productions from Context Free Grammar

Here is a problem I am trying to solve: S -> 0A0 | 1B1 | BB A -> C B -> S | A C -> S | e I know that C is nullable (since it produces an epsilon) and ...
0
votes
1answer
38 views

Given family of grammars, determine if LR(k)

Parsing family of grammars, determine if LR(k) I have the exact same problem, but my reputation is not enough to comment on that thread, plus the OP hasn't been online in 2 years so I can't ask him ...
-1
votes
1answer
55 views

Proving correctness of a CFG by induction on length of strings generated [duplicate]

Consider the following grammar with starting symbol of $S$. $$S \rightarrow 0S11\;|\;S1\;|\;0$$ Let $L = \{0^i1^j:\; \ge 1\; and\; j \ge2i-2\}$ . Give a formal proof of the following claim : For all ...
0
votes
0answers
49 views

Designing CFG for sequences of words of which two arbitrary ones are reversals

Let $L$ = {$x_1\#x_2\#...\#x_k$ : $k\;\ge\;1$, each $x_i\;\in\;\{0,1\}^*$ and $\exists i,j$ such that $i < j$ and $x_i$ = $x^R_J$}. For example, $001001\#0010\#100100\#00001$ is in $L$ because ...
0
votes
1answer
35 views

Pierce's Types and Programming Languages : circular definition of terms?

In Pierce's book, on page 26-27 it is given a definition of terms for a simple language using inference rules. In the picture below it is marked by red highlighting the problematic part. What is ...
3
votes
1answer
92 views

How to convert a grammar with finitely many ambiguous strings into a new, unambiguous grammar?

Suppose $L$ is an infinite CFL, and $G$ is a grammar with finitely many ambiguous strings which generates $L$. Is it possible to convert $G$ into an unambiguous grammar which also generates $L$? If ...
0
votes
1answer
23 views

Reversing a List from a Context-Free Grammar

Let's say I have a struct_declaration_list of the following type. How do I reverse it? ...
0
votes
1answer
73 views

Why are types and grammar non-terminals so distinct?

Sorry ahead of time if some of my terminology is inaccurate, my formal training isn't quite to the level it should be. Almost all programming languages with types separate built-in functions ...
1
vote
2answers
80 views

Converting to CFG from a CFL? [duplicate]

I am trying to learn CFG. Now to make a CFG from a CFL it is really difficult for me. Is there any simple rule or steps so that I can easily find a CFG for a CFL. I am trying to solve one problem ...
5
votes
3answers
98 views

Prove that the complements of pumping-style languages are context-free

Define $L = L(u,v,x,y,z) = \{uv^ixy^iz : i \geq 0\}$, with $u,v,x,y,z \in \Sigma^*$. Prove that $\overline{L}$ is a CFL for all $u, v, x, y, z$ Clearly, $L$ is a CFL, as it is generated by the ...
0
votes
1answer
56 views

How do I use induction to show that the language of a grammar is contained in a given set? [duplicate]

Given that I have the grammar $\qquad\displaystyle G_1 = (\{a, b, c, d\}, \{S, X, Y \}, S, \{S → XY, X → aXb, X → ab, Y → cYd, Y → cd\})$, how am I supposed to prove that $\qquad\displaystyle S(G1) ...
3
votes
2answers
182 views

Recursive descent parser with backtracking for the grammar $S \rightarrow aSa\ |\ aa$

Can someone enlighten me why a recursive descent parser with backtracking that tries the productions $S \rightarrow aSa$ and $S \rightarrow aa$ (in that order) does not recognize the language formed ...
1
vote
1answer
103 views

Find a CFG for the set of prefixes of a CFL [duplicate]

How do i generate grammar for Prefix of Langauge L, SupposeG=(V,􏰀,P,S)is a context-free grammar generating a CFL L then pref(L) is defined as pref(L)={x∈􏰀∗ : ∃ y such that xy∈L}. I understand for ...
3
votes
1answer
64 views

Creating a CFG that connects lengths of three blocks [duplicate]

I have to create a CFG which generates $$\{a^n (ab)^n c^m d^\ell e^k \mid n>0, k, \ell, m\ge0, k<m, m=\ell+k\}$$ The first part is easy enough, I came up with $$\begin{align*} S &\to ...