Questions about formal grammars, generative descriptions of formal languages.

learn more… | top users | synonyms (1)

1
vote
1answer
86 views

Unambiguous CFG for $a^ib^j$ where $i \le j \le 2i$

could you please help me for finding an unambiguous CFG for the following expression: $a^ib^j$ where $i \le j \le 2i$
-1
votes
0answers
19 views

solving left recursion in cfg grammer [duplicate]

could anyone please tell in simple terms how to solve left recursion with an example.I looked through web but couldn't get the procedure to remove left recursion.
-2
votes
0answers
23 views

LL(1) and SLR and LLAR challenge

I know: A language is said to be LL(1) if it can be generated by a LL(1) grmmar. It can be shown that LL(1) grammars are not ambiguous and not left-recursive. ...
2
votes
1answer
40 views

Converting decision problems to grammars?

I'm struggling to understand some concepts related to the relationship between language and computability theories. Can we convert decision problems to the corresponding grammars describing the ...
-3
votes
1answer
94 views

Pushdown Automata Challenge

I read one old-midterm exam on Automata. consider: the language that accepted by above pushdown automata is not generated by which of the following grammar? 1) S->aBaa|a$\epsilon$ ...
0
votes
0answers
46 views

LALAR vs SLR Table for Given SLR Grammar

i'm so glad that ask my first question on my favorite site. Infact i ran into multiple choice question in recent exam on Compiler Course. Suppose T1, T2 is created with SLR(1) and LALR(1) for ...
1
vote
1answer
45 views

Are context free grammars the only ones that have parsing trees?

As I understand, the generation process of a string in a context free language according to its context free grammar can be represented as a tree. For a formal language which can have a formal ...
0
votes
2answers
39 views

Are constituency grammars and dependency grammars two different types of context free grammars?

From http://en.wikipedia.org/wiki/Parse_tree A concrete syntax tree or parse tree or parsing tree[1] or derivation tree is an ordered, rooted tree that represents the syntactic structure of a ...
0
votes
1answer
26 views

Grammars: is there some connection between non-terminals $S$ and $S'$?

Given a grammar such as the following, does $S'$ have some special meaning or does it just denote another non-terminal like $B$, $A$, $P$, $Q$ etc.? $$\begin{align*} S &\to aBS'\\ B ...
-1
votes
0answers
46 views

Is this grammar for if-then-else ambiguous?

We have a grammar G for branch commands. Suppose a compiler selects a strategy that uses a parser that recognizes the time of procedure running. Which of following parser could without any change to G ...
-2
votes
0answers
19 views

Remove left-recursion from CFG for binary expressions

I use this grammar for binary expressions: ...
-3
votes
1answer
61 views

Language of a grammar

What's the language of following grammar? $G: S \to S_1B$ $S_1 \to aS_1b$ $bB \to bbbB$ $aS_1b \to aa$ $B \to \lambda$ any hint or solution?
-3
votes
1answer
37 views

Find an unambiguous grammar [closed]

S → aS | aSbS | (empty) where the alphabet is {a,b} in other words, the set of strings where any prefix has at least as many 'a's as 'b's.
1
vote
1answer
41 views

Are all Chomsky-Type3 grammars LL(1)?

Referring to this Question, where an answer is stating that all Type 3 languages are LL(1), I'd like to know if all Type 3 grammars are possibly LL(1). If not, why is it so? Are there maybe ambiguous ...
-2
votes
1answer
39 views

Generative grammars and analytic grammars?

What are a generative grammar and an analytic grammar? How are they different from a formal grammar? Is the recursive definition of the language of a propositional calculus, a first order logic ...
1
vote
1answer
75 views

What are the meanings of metalanguage and metasyntax and EBNF?

I am trying to understand what BNF, metalanguage, and metasyntax are. From https://proofwiki.org/wiki/Definition:Metalanguage A metalanguage of a formal language is a formal language used to ...
7
votes
2answers
154 views

Generating a set of minimal-length strings that, together, invoke every production of a context free language

Problem (tl;dr) Given a context free grammar, $G$, find a set of strings that take $G$ through every production it has at least once. How and how fast can it be done? Background I'm working on a ...
-5
votes
1answer
34 views

What is the language generated by the following grammar? [closed]

Could please tell me the language generated by this grammar? S->iS |iSeS|ε
-5
votes
1answer
30 views

Show that this grammar is ambiguous [closed]

$E\rightarrow E+E | E*E | \neg E | (E) | num$ prove the above grammar is ambiguous by giving 2 different parse trees for the expression 4*(~3+5)
3
votes
0answers
75 views

Recursive-descent parser for the grammar S -> S(S)S | ε

I'm studying (for self-betterment - I don't go to school) the 2nd edition of Compilers: Principles, Techniques and Tools by Aho et al. I'm not sure how to do Exercise 2.4.1 (b), which is to construct ...
1
vote
0answers
61 views

LL(1) grammar for postfix ternary operations

Suppose the task is to make an LL(1) grammar for postfix operations, where the only operation is ternary. Obvious approach is $N$ - number $O$ - operation $S$ - expression ...
-3
votes
2answers
79 views

Grammar for a language with 1/3 of a's

I have this language: $$ L = \left\{ w \in \{a,b,c\}^* \;\big|\; |w| / |w|_a = 3 \right\} $$ where $|w|_a$ is the number of occurrences of $a$. How can I find a grammar that generates it?
2
votes
1answer
76 views

Can every DCFG be converted to DGNF?

I know you can convert every context-free grammar into Greibach normal form grammar. But can I convert every deterministic context-free grammar into deterministic Greibach normal form grammar?
3
votes
2answers
98 views

Correspondence between automata and formal grammars?

From Wikipedia Since there is a one-to-one correspondence between linear-bounded automata and such grammars, no more tape than that occupied by the original string is necessary for the string ...
5
votes
2answers
472 views

does every CFL have an ambiguous CFG?

some questions have been popping up recently on ambiguity in CFLs/CFGs which can have subtleties (eg languages vs grammars & ambiguity vs inherent ambiguity). wikipedia states: Many [context ...
1
vote
1answer
105 views

Resolve left-rescursion

Can anybody give me a hint on how to get rid of the left recursion in the following grammar? $$A \rightarrow B \mid a$$ $$B \rightarrow b \mid C \mid D \mid E \mid F \mid G$$ $$C \rightarrow c \mid A ...
3
votes
0answers
43 views

Automatic tool for resolving left-recursion within CFG [closed]

Though facing the fear that someone might not like my question but does somebody know a useful tool to either resolve left recursion or to simplify a context-free grammar automatically ? I need ...
1
vote
2answers
121 views

Syntax and formal grammar of a formal language

For a formal language, I wonder what differences and relations are between its syntax and its formal grammar. A formal grammar is a set of formation rules that describe how to generate the strings ...
1
vote
1answer
30 views

Multiple production rules for expressions of the same type?

I often see syntax like ...
-1
votes
1answer
31 views

Construct grammar given the following language [duplicate]

Construct grammar given the following language! $ L = \{(ab)^{n+1}u(ba)^n|n>0, l_c(u) = 1, u\in\{a,c,d\}^* \}$ My interpretation in a less accurate way: $(ab)^{n+1}$ says we need to concatenate ...
0
votes
3answers
115 views

Build a regular grammar for a regular language [duplicate]

The language considered is the infinite set of all chains that meet the following conditions. Conditions: ...
-1
votes
1answer
49 views

How to eliminate the left recursion [closed]

I've read the rules, but can't apply them to this grammar S -> SS S -> (S) S -> () Could anyone provide some detailed explanation ?
0
votes
1answer
60 views

Computing FOLLOW sets for a LL(1) grammar

I am trying to learn compiler design. But I get confused when I have to deal with Follow set specifically for the empty word. I am trying to figure this out please help me with the same. ...
0
votes
1answer
35 views

Is my grammar correct for this context-free language?

$\{a^nb^2a^n \mid n \ge0\}$ I'm studying for my final and I came across this language. I haven't dealt with characters of the same length on opposite ends with something in between. I came up with ...
3
votes
0answers
55 views

Prove or disprove that every $L$ in this class is a CFL iff $L$ is equivalent to a substitution

Let $L$ be a language with every string of the form $(w_i\#)^*$ with $w_i\in\{0,1\}^*$. Set $w'\sim w$ if there is a permutation $\pi_1$ such that $w_i=w'_{\pi_1(i)}$ for all $i$. If additionally ...
1
vote
1answer
61 views

Constructing an unrestricted grammar for a^n b^m c^n d^m [closed]

I've been trying to construct an unrestricted grammar which has the language: L = {a^n b^m c^n d^m | n>0, m>0} But I can't seem to figure it out without ...
3
votes
1answer
100 views

A Question from Introduction to Formal Languages by Gyorgy E. Revesz; Exercise 1.1

The exercise says "Show that the grammar $G = \langle\{S\}, \{a, b\}, S, \{S \to \lambda, S \to aSb\}\rangle$ generates the language $L = \{a^i b^i \mid i = 0, 1, 2, \ldots\}$." Now, I'm new to ...
2
votes
1answer
62 views

parsing at semantic level due to ambiguities

I have a VHDL elaboration engine/simulator. As I understand it, the language syntax allows for ambiguities at syntax level. That is, an assignment ...
2
votes
1answer
68 views

Chomsky normal form: epsilon rule

I have pretty simple question, but still can't find an answer just googling it. I'm trying to understand Chomsky Normal Form (CNF). There are three production rules: $A \to BC$ $A \to \alpha$ $S ...
1
vote
0answers
30 views

Phrase Structure Grammar without rules [closed]

$L = \{a^i b^j c^i d^j | i, j \geq 1\}$ , it has two loops that are the same , I tried alot finding the proper grammar but I got confused and tired What's the Grammar? Can anyone help please???
1
vote
2answers
48 views

Grammar for parsing simple mathematical expression

mexp ::= (< mexp >) | < mexp >< mathlowop >< mexp > | < mulexp > | < float > | < var > mulexp ::= < mexp >< mathhighop >< mexp > mathlowop ::= + | - mathhighop ::= / | ...
1
vote
1answer
51 views

How to check ambiguity of a specific grammar

Giving the following Grammar: S → ^ | SaSMSM | SMSaSM | SMSMSa M → b | c ^ means eopsilon. How can i check whether its ambgious or not? My intuition is ...
0
votes
2answers
78 views

Find a CFG for a language

In an assignment I've been asked to find a CFG for $a^x b^y a^z b^w$, where, $x,y,z,w \in \mathbb{N}^+$, $y > x$, $z > w$, and $x+z = y+w$. A hint was given, think of the language as $(a^p ...
-1
votes
1answer
46 views

Show L is not context free using the CFL pumping lemma

I am trying to use the pumping lemma to show this language is not context free: $L = a^nb^{n+1}c^{2n} : n \ge 0$ So I took $z = a^mb^{m+1}c^{2m}$ where $|z| = 4m+1 > m$. We can decompose $z = ...
3
votes
2answers
264 views

Proving that a word is *not* generated by a context-free grammar

I saw the answer in one of the solutions and I cannot figure out how they got the answer. The question is asked if the word is in the language or not for CNF... How did they get the answer so that ab ...
2
votes
0answers
93 views

Good introductions to Formal Language Theory and Formal Grammars

Does anyone know any good introductions to Formal Language theory and Formal Grammar, that cover the mathematical basis of Syntax and things like context free grammars and pushdown automata. In ...
3
votes
3answers
86 views

Compression of non-adjacent structure using grammar

I'm working with compression algorithms that use context-free grammars (e.g. RE-PAIR and SEQUITUR). These grammars look for frequently occurring digrams (pairs of adjacent symbols) in an input string ...
3
votes
1answer
40 views

grammatical complexity of propositional and monadic predicate validities? (and grammars for recursive but not context-sensitive languages?)

Consider two sets: the set of validities of propositional logic and the set of validities of monadic predicate logic. Call the first set $VP$ and the second set $VQM$. Both of these sets are ...
1
vote
3answers
254 views

How to find whether a grammar's language is finite or infinite?

I have this context-free grammar and I want to find out whether its language is finite or infinite. ...
1
vote
1answer
48 views

Why does left recursion have to be eliminated? [closed]

For example, Let the Grammar be: S->Sa|B Thus, S->Sa->Saa->...->Saa...aaa->Baa...aaa What's wrong with ...