Questions about formal grammars, generative descriptions of formal languages.

learn more… | top users | synonyms (1)

2
votes
1answer
38 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
29 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 ...
-2
votes
0answers
22 views

How to find the shortest common element between two sets generated by a grammar? [on hold]

Suppose I define two grammars: A = N | L (L A) B = N | L (L (L B)) Where A and B are recursive definitions, so ...
1
vote
0answers
27 views

Phrase Structure Grammar without rules [on hold]

$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???
-3
votes
0answers
27 views

Grammar for permutation [closed]

What is the minimal automation that can parse a string abab into following AST? How should the grammar look like?
1
vote
2answers
33 views

Grammar for parsing simple mathematical expression

mexp ::= (< mexp >) | < mexp >< mathlowop >< mexp > | < mulexp > | < float > | < var > mulexp ::= < mexp >< mathhighop >< mexp > mathlowop ::= + | - mathhighop ::= / | ...
1
vote
1answer
38 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
50 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
34 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
218 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
55 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
72 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
35 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 ...
0
votes
3answers
146 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
0answers
35 views

A construction to show a very restricted substitution closure result for DCFLs

Let $P$ be a deterministic PDA recognizing a deterministic CFL with a binary alphabet. Modify $P$ to identify its reading states (denote this subset of states by $R$) in accordance with the ...
1
vote
1answer
34 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 ...
1
vote
2answers
100 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\}$$
0
votes
2answers
59 views

How many states when converting CFG to PDA

When converting a CFG to a PDA I know that you get three main states, Qstart, Qloop and Qaccept. But Qloops will need a various amount of states, and my question is how many? Is there a way to find ...
0
votes
1answer
49 views

Can a context free grammar for $L$, generate a string not in $L$?

from Sipster's definition: Any language that can be generated by some context-free grammar (call it $G$) is called a context-free language (CFL). However, can $G$ generate strings that are not in the ...
1
vote
0answers
30 views

Prove a language is context-free [closed]

for this problem, it asks to prove that A and B are context free, however the CFL pumping lemma doesn't prove that. It proves when languages are not context free. Would the easiest way to prove ...
0
votes
1answer
24 views

Construct context free grammar from language

I have been starting to learn about CFGs and PDAs and have gotten familiar with the simple stuff. I have been able to construct CFGs for simple languages but this question is more specific: $\lbrace ...
2
votes
1answer
37 views

Complement DCFGs and handles

If I have a DCFG G for some language over {0,1}* and a DCFG H for its complement, with disjoint non-terminals, and a (perhaps partially reduced) string, can they both have a handle for the string? So ...
3
votes
2answers
81 views

Defining a context-free grammar for $\{w \in \{0, 1\}^* : \#_0(w) = \#_1(w)\}$ [duplicate]

I have a language where each string in the language has even amount of $0$'s as $1$'s (e.g., $0101$, $1010$, $1100$, $0011$, $10$ are all in the language). I was hoping to define a context-free ...
1
vote
0answers
44 views

Designing a different grammer that generates same expression [duplicate]

I've a set of grammar rules like this: $$ \begin{align*} &S \to AbB \\ &A \to aA|\epsilon \\ &B \to aB|bB|\epsilon \end{align*} $$ The grammar generates the following words: $$ ...
3
votes
1answer
99 views

Simplification of CFG

Recently i was studying removal of useless symbols in productions given in Ullman Hopcroft. The grammar goes as follows S-> aAa | aBC A -> aS | bD B - > aBa | b C-> abb | DD D -> aDa In the ...
2
votes
0answers
38 views

What kind of structural features of strings can be described by regular grammars?

Context-free grammars, as well as other types of grammars, can naturally associate structure with the strings of the defined language, for example tree structures in the case of context-free language. ...
0
votes
1answer
67 views

How to generate the LR(0) finite state machine for a grammar

Here is a context-free grammar with a single nonterminal symbol S and three terminal symbols +, *, and s: S -> + S S | * S S| s My purpose is to build the LR state machine for this grammar. My ...
1
vote
2answers
51 views

What type of recursion is this?

I was trying to rule out whether this was LL(1) by checking for left-recursion in the following grammar: $\qquad A \to 0 A 1 \mid 0 1$ Which produces: $\qquad 0 A 1 \Rightarrow 0 0 A 1 1 ...
-1
votes
1answer
36 views

Left Linear Grammar: How to construct?

I need help constructing a Left Linear grammar for the language $L = \{ a^n b^m c^p \mid n\geq 2, m\geq 3, p\geq 4 \}$ Here is what I have so far, I know : $N = \{S\}$ $T = \{ a, b, c \}$ $P = ...
0
votes
2answers
112 views

What Do Logical Operators In a Grammar Mean?

Is there a way to figure out what the following CFG accepts? $\qquad\begin{align} S &\to S \vee T \mid T \\ T &\to T \wedge F \mid F \\ F &\to p \mid\; \thicksim p \end{align}$ ...
0
votes
2answers
49 views

Which Type of Grammar is this?

I am learning Compiler Design. Can somebody explain what type of Grammar this is? The answer given is $LL(1)$ but there exists a left recursion in the grammar so it cannot be $LL(1)$. I derived the ...
0
votes
0answers
54 views

Remove direct left recursion and common prefixes

I have this grammar and I have to remove direct left recursion and common prefixes. This is the grammar: $\qquad\displaystyle S \to SSA \mid SSB \mid SSC \mid AS \mid A$ this is what I did: ...
1
vote
3answers
97 views

Determining if a context-free grammar produces even-length strings [closed]

Given a context-free grammar, is there an algorithm to determine if the CFG will ever produce an even length string? Or is this undecidable?
0
votes
1answer
64 views

Is this grammar LL(1)?

Consider following grammar: $$X\to Yc|ZY$$ $$Y\to ab|cX$$ $$Z\to d|\epsilon$$ Can this be converted to LL(1)? Cleary, its not LL(1) because of First/First conflict at first production. Can anyone ...
2
votes
0answers
59 views

Why CFG can specify structure of sentence but Regular grammar cannot? [duplicate]

CFG can specify structure of sentences but Regular grammar can only specify strings sequentially. Is it because DFA has only one bit memory?
0
votes
2answers
78 views

Is $a^{n+m}b^{n}c^{m}$ context free?

Language: $ L = a^{n+m}b^{n}c^{m} $ As per a recent test I gave, this language is not context free. However, I think it is. Corresponding Grammar: $ X \rightarrow aXY \space |\space \epsilon $ $ ...
0
votes
0answers
39 views

Find the language generated by a grammar

I have to find the language generated by the grammar: $\qquad\begin{align*} S &\to SA \mid a \\ A &\to aAa \mid bA \mid \varepsilon \end{align*}$ where $\varepsilon$ is the empty ...
0
votes
0answers
13 views

Unambiguous Context free Grammar [duplicate]

I was reading through Context Free Grammar, and I came across ambiguous grammar. If the language produced by CFG has more then 1 parse tree, then CFG is an ambiguous grammar. Is there any way by which ...
1
vote
1answer
28 views

Indentation based Grammars

Considering programming languages with significant whitespace for indentation, such as Python or Haskell. How does this whitespace fit into the grand schemes of programming language grammars. I can ...
0
votes
2answers
174 views

Drawing Annotated Parse Tree for Syntax Directed Definition [closed]

Im trying to draw an annotated parse tree for 3*5+4n, the text book shows the following: [Compilers - Principles, techniques and tools (Dragon Book) by Aho, p308] ...
1
vote
1answer
93 views

Is this grammar LR(1)

I am reading parser chapter from dragon book and I found a grammar over there - $ S \rightarrow L=R $ $ S \rightarrow R $ $L \rightarrow *R $ $L \rightarrow id $ $R \rightarrow L $ Now I have ...
0
votes
0answers
44 views

Is this a grammar for arithmetic expressions?

Describe the language generated by the following grammar <A> ::= <A><A> '+' | <A><A> '*' | 'a' So it's not too hard to see ...
6
votes
1answer
164 views

Why is ww a linear indexed language while www is not?

I am a little bit confused on one idea regarding indexed languages. $\{ww \mid w \in \{a,b,c\}^* \}$ is a linear indexed language, but $\{www \mid w \in \{a,b,c\}^* \}$ is not a linear ...
3
votes
2answers
158 views

How to get 2-state PDA for CFG?

I'm studying for my Computing languages test and there's one idea I'm having problems wrapping my head around, as far as I know for any Context Free Grammar (CFG), we can design a 2-state Pushdown ...
1
vote
1answer
35 views

Eliminating $\varepsilon$-productions during elimination of left recursion

I'm following the algorithm for left recursion elimination from a grammar. It says remove the epsilon production if there is any. I have the grammar $\qquad S \to Aa \mid b$ $\qquad A \to Ac \mid Sd ...
0
votes
1answer
130 views

Is this language context free?

In a recent test, I was asked to recognize if the below language is context free: $\qquad\displaystyle L = \{0^{n+m}1^{n+m}0^m \mid n,m \geq 0\}$ I think it is context free, and can be accepted by ...
1
vote
2answers
47 views

Need solution for infinite right recursive grammar in Predictive parsing?

i am new to compiler design, currently studying Ullmans book on this.He says: Problem with predictive parsing (both recursive and non recursive) is that Left recursive productions can go infinite ...
1
vote
3answers
55 views

Why isn't every monotonic grammar context sensitive free?

The question is really confusing me. I know every context sensitive grammar is monotonic but not vice versa. e.g. AB--->BA is monotonic but not context sensitive. Can someone explain to me in simple ...
-1
votes
1answer
217 views

Rice Theorem - What is non-trivial property? [duplicate]

Every nontrivial property of the recursively enumerable languages is undecidable. What exactly is nontrivial property?
1
vote
0answers
32 views

Is this theorem about left-factored grammars correct?

I am working on CFG grammars, LL grammars in particular and I encountered the following theorem in the slides of presentations written by my professor: A CFG grammar cannot be left-factored if all ...