Questions tagged [formal-grammars]

Questions about formal grammars, generative descriptions of formal languages.

Filter by
Sorted by
Tagged with
0
votes
1answer
36 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
15 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 ...
0
votes
1answer
44 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: ...
3
votes
1answer
124 views

When did “regular” start referring to Type 3 languages/grammars?

In his 1959 paper, On Certain Formal Properties of Grammars, Chomsky defined a "regular" grammar as a specific form of a type 2 (context-free) grammar. (See Definition 8 of that paper.) He then goes ...
0
votes
2answers
26 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 ...
1
vote
0answers
49 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
40 views

left/right derivations of grammars and parse trees

I'm having a hard time understanding how left/right derivations work. I have a very simple example that I've attempted but I don't really know how to check if it's correct. $S-> NP$ $V$ $NP$ $NP -&...
0
votes
1answer
22 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
41 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\}$?
-2
votes
0answers
39 views

Is this grammar context-free? What strings does it generate?

Is this grammar context-free? (Thanks! Someone pointed out it's context-sensitive because there's more than one Non-terminal on the left) What strings does it generate? (...
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 ...
0
votes
1answer
15 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?
0
votes
2answers
191 views

Is this an LL(1) grammar? How to solve First - Follow conflict?

im trying to check if this grammar is LL(1). S -> L = R L -> * L | id R -> L | R + R | num As you can see there is a Left recursion on R production. So i remove that and what i get is: S -> L = ...
0
votes
1answer
54 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’ ’...
2
votes
1answer
43 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 ...
9
votes
1answer
25k views

Convert CFG to PDA

Is there any set of rules or methods to convert any context free grammar to a push down automata? I already found some slides online but I wasn't able to understand them. In slide 10 he speaks ...
10
votes
5answers
2k 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 ...
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
34 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
17 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
64 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 ...
1
vote
1answer
55 views

What complexity class is this set of grammars? In between NL and P?

Given a grammar where (every rule has the form $X \to YZ$, $XY \to Z$ or $X \to a$), (($X \to YZ$) implies ($X \to ZY$)) and (($XY \to Z$) implies ($YX \to Z$)) where $X,Y,Z$ range over nonterminals ...
0
votes
1answer
36 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 ...
0
votes
2answers
3k views

Removing epsilon transition from context-free grammar

I have the following context-free grammar from which I have to remove epsilon transitions: $S \to 0A0|0$ $A \to BC|2| CCC$ $B \to 1C | 3D | \epsilon$ $C \to AA3 | \epsilon$ $D \to AAB | 2$ By ...
1
vote
1answer
36 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
vote
1answer
75 views

Derivation from grammar

Given the grammar $G=(\{S, L_x, R_x, W_x\}, \{a,b\}, P, S)$ derive the words $abaaba$ and $aabbaabb$. $$ P=\left\{ \begin{align}S\phantom{{}_x R_y} &\to \epsilon \mid L_x R_x,\\ L_x \...
1
vote
1answer
36 views

Finding a grammar for $L=\{a^nb^mc^rd^s| n+m<r+s\}$

I am trying to find a grammar for $L=\{a^nb^mc^rd^s| n+m<r+s\}$, which has the hint of it having "some similarity" to $L=\{a^ib^j|i<j\}$ This last one is quite easy to get ($S\to aSb | ...
2
votes
4answers
73 views

If $L$ is regular then $L^{|2|}=\{w_1w_2 \mid w_1,w_2\in L, |w_1|=|w_2|\}$ is context-free

I have found a problem about proving whether $L^{|2|}=\{w_1w_2 \mid w_1,w_2\in L, |w_1|=|w_2|\}$ is context-free or not, knowing that $L$ is regular So far I know that: There are examples where $L$ ...
1
vote
2answers
61 views

Finding a grammar for $L = \{ 0^x1^y0^z1^w | x+w=y+z\}$

I have found an exercise where it tasks to provide a grammar and a pushdown automata for $L = \{ 0^x1^y0^z1^w | x+w=y+z\}$ While finding a pushdown automata for it is quite easy (four states and two ...
10
votes
1answer
366 views

Shift-resolve parsing - questions

I've recently came across a paper describing the parsing technique mentioned in the title. Unfortunately, the terminology used in said paper is somewhat beyond my comprehension, so I've been ...
1
vote
2answers
185 views

Trying to remove ϵ rules from a formal grammar resulted in L(G) ≠ L(G')

I am trying to remove ϵ rules from the following grammar (after applying the remove redundant symbols algorithm): $G = (\{S,A,B,C\},\{0,1\},P,S)$, where the productions are \begin{align} &S \to AB ...
3
votes
1answer
45 views

Is there a method to generate the complement of a context-free grammar?

Given the languages $L_0 = {w \in \{0,1\}^*}$ such that $w$ is a palindrome and $L_1 = {w \in \{0,1\}^*}$ such that $w$ is not a palindrome, meaning $L_1$ is the complement of $L_0$, we want to find ...
0
votes
1answer
25 views

Is the complement of the language generated by $S \to aSbS|\epsilon$ context-free?

How is it possible to prove whether the language $\{a, b\}^{∗} \setminus \{S → ε, S → aSbS\}$ is context free?
0
votes
2answers
145 views

How to remove null production from context free grammar?

How to remove null production and simply the grammar? $$ S \to a \mid Ab \mid aBa \\ A \to b \mid \epsilon \\ B \to b \mid A $$ Can the simplification result in this CFG? $$ S \to a \mid aBa \\ A \to ...
2
votes
2answers
531 views

What are the modern alternatives to Backus–Naur form and what are their advantages?

I am very new to the whole concept of context-free grammars to represent the syntax tree of formal languages (i.e., programming languages). It seems that the Backus–Naur form (BNF) is the oldest of ...
0
votes
1answer
445 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 ...
1
vote
3answers
896 views

Context-free grammar for binary words

I am supposed to create CFG for this languague: $L= \{w : w \in \{a, b\}^*, |w_b| = 3k, k \geq 0 \}$ where $|w_b|$ is count of terminals $b$ in $w$. For example: aa - OK, no 'b' abb - wrong, only ...
4
votes
1answer
229 views

Context-free grammar for all words not of the form w#w

I was asked to define a CFG for the complement of $\{w\#w \mid w \in \{0,1\}^*\}$ and I'm struggling to define it. I think it is quite similar to defining a CFG for the complement of $\{ww \mid w \in \...
2
votes
1answer
253 views

Negative lookahead in LR parsing algorithm

Consider such a rule in grammar for an LR-family parsing generator (e.g YACC, BISON, etc.): Nonterminal : [ lookahead not in {Terminal1, ..., TerminalN} ] Rule ; ...
1
vote
1answer
30 views

Trying to find two CFGs for the following languages

I'm trying to get CFGs for these two languages which still remain unsolved in my practice problems sheet: $L = \{ a^kb^ra^m | m=k+r\}$ $L = \{ a^nb^m | 1\leq n\leq 2m\}$ With the first one, I thought ...
0
votes
1answer
517 views

LL1 parsing algorithm for strings generated by a given grammar

How to describe a $\operatorname{LL(1)}$ parsing algorithm for strings generated by a given grammar? I have to design a parser for a specific grammar. Let $G$ be the grammar described as: $$S \...
0
votes
1answer
27 views

How can Chomsky hierarchy be applied to languages with alternated letters?

I have the following grammar, which I know it is regular because it can be represented by a finite state automata: \begin{array}{l} \mathrm{S} \rightarrow \mathrm{X} \mid \mathrm{Y} \\ \mathrm{X} \...
0
votes
1answer
40 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 $\}...
1
vote
1answer
54 views

How do you create a sentential form in a given grammar?

I am given the following grammar: $$S ::= aBS| abT |a$$ $$T::= d | dT$$$$B ::= da | ϵ | S$$ I need to decide whether $aBaabda$ can be produced in the given grammar. I am unsure how the grammar can ...
2
votes
2answers
3k views

Find a context-free grammar for the language $L=\{a^nb^m\mid 2n<m<3n\}$ [closed]

I need to find a context-free grammar for the following language which uses the alphabet $\{a, b\}$ $$L=\{a^nb^m\mid 2n<m<3n\}$$
14
votes
1answer
481 views

Is the language of words that are unbalanced in the first half context-free?

(Practice exam question in computational models) Definition: A word $w\in \{0,1\}^*$ is called balanced if it contains the same number of $0$s as $1$s. Let $L = \{w\in \{0,1\}^*\mid |w|$ is even and ...
2
votes
1answer
981 views

Can the common algorithm to convert to Chomsky Normal Form result in “useless” productions?

I have an example below which seems to lead to a “useless” production. This is the original grammar: \begin{align*} S&\longrightarrow aX\,|\,Yb\\ X&\longrightarrow S\,...
0
votes
0answers
22 views

Building Context sensitive grammars?

I just discovered Context-sensitive grammars. The problem is most of the examples are weird non-interesting toy languages ! Second the descriptions are math oriented, rather than programmer oriented. ...
0
votes
0answers
26 views

Parsing a context free grammar, Backus Naur question

Does anyone know how BNF rules expecting the empty string ($\epsilon$ or the "") behave during creation of a parse tree using grammar from a string of ...
0
votes
1answer
317 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 (...

1
2 3 4 5
22