Questions tagged [formal-grammars]

Questions about formal grammars, generative descriptions of formal languages.

Filter by
Sorted by
Tagged with
-3
votes
0answers
18 views

how to construct right-linear grammar

I do not succeed in this question: $S \rightarrow Rc\,|\,q_fb\,|\,b$ $R \rightarrow Rc\,|\,q_fa\,|\,a$ $q_f \rightarrow q_fa\,|\,a$ Need to construct a right-linear grammar Would appreciate help :)
1
vote
0answers
39 views

Checking correctness of grammar for $L = \{w \in \{a, b\}^* \text{ }| \text{ } w \text{ has } n_a(w) = 2n_b(w)\} $

I have written a CFG that supposedly generates $L$ below. $$L = \{w \in \{a, b\}^* \text{ }| \text{ } w \text{ has } n_a(w) = 2n_b(w)\}$$ Where $n_a(w)$ is the number of $a$'s in $w$ and similarly for ...
0
votes
0answers
19 views

Algorithmically find a formal grammar for a recursively enumerable formal language

The algorithmic problem is as follows. The input is the source code of a program accepting an integer as input and outputting a finite binary sequence. This program defines a recursively enumerable ...
-4
votes
0answers
12 views

Give CFG for the language $L=\{0^i1^j0^j1^i|i,j\geq 0\}$ [duplicate]

Give CFG for the language $L=\{0^i1^j0^j1^i|i,j\geq 0\}$ I have no idea
1
vote
2answers
56 views

Are decidable set/languages EQUIVALENT to type 1 grammars (non-contracting)?

Suppose a Turing Machine (TM_G) that generates natural numbers following < or, equivalently, it generates words in lexicographical order. Then, that language/set is decidable. Because it is trivial ...
3
votes
1answer
53 views

Existence of a CFL $L$ such that $\sqrt{L}$ is not CFL

Does there exist a CFL L such that the language defined as $L' = \sqrt{L} = \{w | ww \in L\}$ is not CFL? I feel that there is no such $L$ but obviously, I am unable to prove it. I am sorry but I have ...
1
vote
0answers
11 views

How do bottom up parser evaluate things that need an inherited attribute?

I learned that Bottom up parsers use only synthesized attributes to evaluate semantics. Which makes sense considering that it would be very hard to evaluate an inherited attribute in bottom up ...
0
votes
1answer
21 views

Context free grammar transformation to Normal Form

I found a task where you need to transform context free grammar to normal form. I'm a High Shcool student at this moment. But my Brother learning this at the university. He don't have much time to ...
0
votes
1answer
33 views

Grammar for $\{a^n b^n c^m d^m \mid n \geq 1, m \geq 0\}$

I'm trying to understand how the construction of simple grammars works. In my textbook, there's the following example I am supposed to find a grammar for: Let $L_1= \{a^n b^n c^m d^m \mid n \geq 1, m ...
3
votes
1answer
741 views

Can a language be context free and not have a BNF grammar?

Leslie Lamport claims that TLA+ is too complex to be described in BNF. Does that mean TLA+ is not a context free language? What is the relationship between the set of context free languages and the ...
0
votes
1answer
45 views

Grammar for $L=\{a^{i+1}b^{i}c^{2j}d^je^{2j}|i,j>0\}$

I'm supposed to write grammar for this language: $$L=\{a^{i+1}b^{i}c^{2j}d^je^{2j}\mid i,j>0\}$$ This is what I have so far: $$\begin{align} S &\to aXbY \; \\ X &\to aXb \;|\; a \\ Y &\...
-2
votes
0answers
31 views

I'm confused on how to test for LL(K) grammar

I have several of these I need to test if they are LL(K) grammars. I'm very confused on how to do this and how to search ahead. Help please. ...
0
votes
1answer
26 views

Proving that a language defined by a regular expression is equivalent to a right linear grammar

After thinking for a bit, I am not able to prove a double inclusion proof for the following problem. It seems very interesting to me. Consider the regular expression $r= ((1(00)^∗1 + 0)1)^∗$ and the ...
1
vote
2answers
50 views

Proving that $X\to aX|Y$, $Y \to Yab|b$ is unambiguous

Prove that the following grammar is unambiguous: $$X \to aX | Y$$ $$Y \to Yab | b$$ I know that I must prove that the strings produced by this grammar have only one parse tree, but how can I do this?...
0
votes
1answer
21 views

BNF syntax for a recursive function?

I'm to write a syntax that will allow for a recursive function, i.e. f(x) = if x == 0 then x else f(x+1) Here's one attempt at creating the grammar: But I don't ...
3
votes
2answers
666 views

Why does the Java grammar have a StatementExpression that resolves to just Expression? Why have this and other redundant rules in the grammar?

I'm looking at the following grammar rules for the Java language described on the Oracle docs: ...
-1
votes
0answers
19 views

Is my context free grammar of this language right?

L = { a^m b^n a^o a^p b^q : m >= n, o >= p + q } That's what I tried to do: S -> aSb|bSa|A A -> aA|ε Is my CFG right? I'm missing something? My difficult it's in this part o >= p + q
-1
votes
1answer
42 views

CFG for $L=\{a^m b^n c^k | m,n,k > 0, k\neq m+n\}$

I started learning CFG and I'm trying to find CFG for this language, but I have no idea where to start and I can't seem to find this one online anywhere. It would be great help, if someone could show ...
1
vote
0answers
12 views

What to do with operators with the same precedence in an unambiguous grammar?

I'm trying to create an unambiguous grammar for a calculator that uses $+$, $-$, $*$, $/$ and $()$. From watching videos and reading articles online, I understand how to create the grammar with $+$, $*...
1
vote
1answer
34 views

Difficulty in understanding the proof of “Every context-sensitive language L is recursive” as given in the Peter Linz text

I was going through the automata text by Peter Linz. There I came across the proof the theorem below. I could not quite get the portion of the proof in bolds. Every context-sensitive language L is ...
0
votes
0answers
11 views

Difficultly in understanding the construction corresponding how any Turing machine can be mimicked by an unrestricted grammar

I was going through the automata text by Peter Linz where I came across the construction below. To show the converse, we describe how any Turing machine can be mimicked by an unrestricted grammar. We ...
0
votes
0answers
39 views

Eliminating ambiguity in $A \to AA \mid (A) \mid a$

I'm trying to solve this complier design problem related to ambiguity in CFG the given grammar is \begin{align} &A → AA \\ &A → (A) \\ &A → a \end{align} I was able to find that this ...
1
vote
2answers
38 views

Converting a regular expression to a context-free grammar

Does this conversion look right? I am learning conversion from RE to CFG. RE: $$(a \cup b)^* \cup ab(a \cup b)^*$$ CFG: Terminals: $$ S_1 \to a \\ S_2 \to b $$ This is for the first $(a + b)^*$: \...
1
vote
0answers
28 views

Generating a recursive descent parser for grammar having Kleene star

From what I have been taught, I cannot use left-recursive, nondeterministic, or ambiguous grammars in recursive descent parsers. So, here is the grammar: \begin{align} &E \to E+T \mid T \\ &T \...
3
votes
2answers
163 views

Arguing that $L= \{a^n | n\geq 0\} \cup \{a^nb^n| n\geq 0\}$ is not $LL(k)$ for any $k$

Consider the language $L= \{a^n \mid n\geq 0\} \cup \{a^nb^n\mid n\geq 0\}$ and the following statements. $\quad\quad\text{I. }L$ is deterministic context-free. $\quad\quad\text{II. }L$ is context-...
1
vote
2answers
41 views

Language of regular grammar

What is the regular grammar of the language: $$L=\left\{a^nb^nc^md^m\left|n,m\ge 1\right|\right\}\:above\:\Sigma =\left\{a,\:b,\:c,\:d\right\}$$ My attempt: $$S\rightarrow aAbcBd|aXd$$ $$A\rightarrow ...
1
vote
1answer
30 views

Grammar for all words other than $wq,qw$

I want to generate a grammar that can't generate the words $qw$ and $wq$ but can generate the word $qwwq$. In other words, $L(G)=\{m ∈ \{q,w\}^* \mid m \neq wq,qw \}$. My grammar: \begin{align} &S ...
0
votes
1answer
23 views

Words which, cyclically shifted twice, equal their reverse

Let the alphabet be $Σ = \{0, 1\}$. For any string $w ∈ Σ^*$ of length at least 2, define the operation $C_2(w)$ to be a cyclic shift of size 2 on $w$. That is, if $w = w_1w_2 \cdots w_n$ with $n ≥ 2$ ...
1
vote
1answer
59 views

Construct a grammar for $\{a^n(bc)^m : m,n \ge 1, m < n/2\}$

I'm new to writing languages in context-free or regular grammar, so I'm struggling how to do this one. It is a bit more complicated that simpler ones I've practiced doing. The problem is to construct ...
0
votes
1answer
27 views

How do I represent this regular expression in regular grammar?

Question: Is the regular expression and regular grammar equivalent? I've look on some examples of regular grammar however I don't think I fully understand how to convert regular expression to its ...
1
vote
1answer
107 views

Constructing a context-free grammar

I want to design a context-free grammar that generates words that either both start and end with $c$, or contain the same amount of $a$-s and $b$-s. Here is what I have. The nonterminals are $S,X,Y$, ...
0
votes
1answer
31 views

Regular set of the “does not contain” kind

Given a language $L$ and a set of strings $\Sigma^* = \{0, 1\}^*$, how can I find a regular set that expresses $L = \{ w \in \Sigma^* \mid w$ ends with $00$ and does not contain $11\}$? Well, the part ...
0
votes
0answers
23 views

How to change a grammar so that it can be unambiguous?

The original grammar is $$ S \to SaS \mid SbS \mid ScS \mid d $$ My answer is $$ S \to daS \mid dbS \mid dcS \mid d $$ Is that correct?
0
votes
0answers
16 views

L= ${ a^mb^nc^pd^q: m+n<>p+q }$ context free? [duplicate]

I cant find the grammar to prove it is context free but. I also tried a PDA but couldnt make it. Can someone suggest a grammar for this?
0
votes
1answer
56 views

Which of the following words is in the language of the grammar G?

This is taken from a practice quiz by my university. I ruled out that aabbbaab is not part of the grammar: S → aSb → aaSbb... This shows that I can't make this word because it would have to have ...
0
votes
0answers
16 views

Why can't I evaluate this L-Attributed SDD with a pre-order traversal?

My powerpoints for a compiler class says "an L-Attributed SDD can be evaluated with a pre-order (root, left, right) traversal", and to be L-Attributed the nodes need to have either ...
1
vote
2answers
37 views

How to evaluate a Kleene's Closure through CFG and attribute grammars

For a CFG with the production rules that can represent a regular expression. How can one calculate all the set of strings that regular expression would produce. For T = {a, b,*,(,)} and an arbitrary ...
0
votes
1answer
48 views

How can I make the following grammar unambiguous

Given the below ambiguous grammar how can I make it inambiguous and how can I prove the new modified unambiguous grammar is unambiguous? S -> S + S | S − S | S ∗ S | S / S | (S) | x | y My attempt: ...
0
votes
1answer
27 views

Formal Grammar: derivation form posted on Wiki?

Wiki describes the binary relation $\underset{\mbox{G}}{\implies}$ as "G derives in one step". I have a question on the condition when there are multiple productions for a single non-...
1
vote
1answer
53 views

Is it possible to make a grammar LL($1$) which recognizes palindroms?

Is it possible to make an algebraic grammar LL($1$) which recognizes palindroms for an alphabet $\{a,b\}$?
0
votes
0answers
18 views

generating strings from this formal grammar [duplicate]

Hey guys I am having trouble generating strings from this language, I haven't seen a grammar that looks like this and can't figure how to generate strings from this grammar, is this Context Sensitive ...
1
vote
0answers
52 views

A Formal Grammar: defining English counting numbers?

I would like to define a grammar that produces and recognizes the counting numbers of the English language. I created the production rules below based on the assumption this is context-free, but I am ...
0
votes
1answer
17 views

Compilers: How to see “the number of grammars where there exists a string that has at least two different left-most derivations”?

Could someone tell why "G1 and G3 are ambiguous" and how to see whether a string has at least two different left-most derivations in general?
2
votes
1answer
44 views

Proof that $L = \{a, b\}^* - \{(a^n b^n)^m \mid n, m \ge 1\}$ is a CFL

I want to prove that $L = \{a, b\}^* - \{(a^n b^n)^m \mid n, m \ge 1\}$ is a Context Free Language. so far, I tried to find a Context Free Grammar for $L$ or to use properties of Context Free ...
0
votes
0answers
20 views

I am trying to design an LL(1) Parser that accepts T = {a, b *, +, ?, E, U, (, ) }

I am trying to design an LL(1) Parser that accepts regular notation where 'E' represents epsilon, and 'U' represents "or" like ' | '. So far I made one that accepts T = { a, b, *, +, (, ), E}...
0
votes
1answer
37 views

Removing left recursion with terminals only

I have a grammar: $G → id > id$    $| id < id$    $| G and id$ Does anybody know how I can do left recursive elimination on this one, when it doesn't have any extra non terminals?
1
vote
0answers
19 views

Compile XPath Abbreviated Query to Unabbreviated version

The Xpath 3.1 presented by W3C includes the full grammar of the language with both abbreviated and unabbreviated syntax. I am interested in references (if any) for any formal work done to compile/...
3
votes
2answers
67 views

Context free grammar for $L = \{w \text{ | }w \in \{a,b\}^*, |w|_a=|w|_b-1\}$

I'm trying to find a grammar for $L = \{w \text{ | }w \in \{a,b\}^*, |w|_a=|w|_b-1\}$, which is proving to be tricky. I know that $L_2 = \{w \text{ | }w \in \{a,b\}^*, |w|_a=|w|_b\}$ has the following ...
0
votes
1answer
49 views

Computing FOLLOW sets of left recursive grammar

Left recursive ambiguous expression Grammar: $E \rightarrow E+E \mid E*E \mid (E) \mid \mathbf i\mathbf d$ I tried computing FIRST and FOLLOW sets of both left recursive grammar and after ...
1
vote
1answer
37 views

Is there a formal language of Combinatory Logic's expressions?

The Combinatory Logic uses expressions of the form (x y) called "applications" (here, we have an "application of x to y"). Thus, the language of CL is a set of "parenthetic ...

1
2 3 4 5
23