Questions about formal grammars, generative descriptions of formal languages.

learn more… | top users | synonyms (1)

2
votes
1answer
29 views

CFG for words that are not a concatenation of the same word [duplicate]

I am teaching myself formal languages, and yesterday i got stuck at an exercise asking for a context free grammar for the language: $ L = \{x \in \Sigma ^{+} | \ \forall w \in \Sigma ^{+} \ x \neq ...
0
votes
1answer
25 views

Attribute grammars: How are attributes implemented?

I've read about attribute grammars, but I haven't found out, how are the attributes often implemented? To me they scream objects (of classes), but they could be also variables. But are there any ...
-1
votes
0answers
27 views

Greibach Normal Form problem

I have this grammar: $S \to AA \mid 0$ $A \to SS \mid 1$ At first there is no left-recursion. So, I go forward to enumerate non-terminals. I get $S=A_1, A=A_2, 0=A_3, 1=A_4$, so $A_1 \to A_2A_2 ...
1
vote
1answer
85 views

Calculi for a computability class

Proving two push down automata equivalent is undecidable. But proving two finite state machines equivalent is decidable. You also cannot write a programming language that allows expressing the ...
1
vote
1answer
26 views

Indirect Left recursion

I'm solving (indirect Left Recursion) for these production rules . S is the starting symbol. S -> Aa / a eq1 A -> Sb / b. eq2 Now I can do this in two ...
0
votes
1answer
39 views

Grammar ambiguous or not?

So I've been struggling for the past hour with $G=(\{S\},\{a,b\},P,S)$ with productions $S\to aaSb | abSbS | \varepsilon$. I need to prove whether this grammar is ambiguous or not. Thus far I think it ...
1
vote
1answer
29 views

Equivalence of regular grammars

I know that proving context free grammars equivalent is undecidable. I also know that proving if a context free grammar recognizes a regular language is undecidable. Here is my question: is proving ...
1
vote
0answers
39 views

How to find conflicts in LALR parser?

I have a LR analyser and I can't find out how to know whether the grammar is or is not LALR(1). I think that I have to merge states with the same rules. So I have to merge states: $2 - 12, 3 - 13, 4 ...
3
votes
2answers
50 views

Is it decidable whether a given context free grammar generates an infinite number of strings?

Is the decision problem "Does a given context free grammar generate an infinite number of strings" decidable? In order to test whether a context free grammar generates an infinite number of strings or ...
3
votes
1answer
135 views

How can I check that the language of one context-free grammar is a subset of a second context-free grammar?

Could you explain me, how can I check, that the language of first context-free grammar (G1) is a subset of the language of second context-free grammar (G2). G1 and G2 are two LL(1) grammars with ...
0
votes
1answer
42 views

How do I derive a regular grammars from this regular expression? [closed]

How do I derive a regular grammars from this regular expression? (a or b)*ba(ba)* I'm stuck with the last part so ...
2
votes
1answer
41 views

Why is my regular grammar for palindromes wrong?

I've seen that people prove somehow that set of all palindromes isn't regular language by using a pumping lemma, which I am not familiar with. I've created grammar which can generate all palindromes ...
1
vote
1answer
48 views

Language of words that begin and end with same symbol and have equal numbers of a's and b's

I wish to find the CFG for a language on two symbols (say a and b) whose words begin and terminate with the same symbol, and have equal quantities of a's and b's. What is the thought process I should ...
3
votes
0answers
30 views

What kind of formal language is generated by Parsing Expression Grammars?

I've been unable to find what language is recognized by PEGs. The original paper[1] only conjectures that there are some Context-Free Grammars that are unrecognizable by PEGs. It also demonstrates how ...
0
votes
1answer
52 views

Why is $L=wxw^R|w,x\in\{0,1\}^+$ regular? [duplicate]

I was taught that if you can create a DFA to accept a language, then the grammar that is generating the language is regular. AND A DFA is a finite automata that accepts a language and also rejects ...
-1
votes
0answers
43 views

How to solve a left-recursive Problem in grammar

I have a grammar like this and it has different type of problems 1) X -->YX|$ 2) Y --> ε|A|let A in Y|let A in E end 3) A--> x=E 4) E-->(E)|E*E|*E|EE|x|ƛx.E I tried to solve that and this my ...
1
vote
1answer
36 views

How to treat ϵ-productions in table-driven predictive parsing?

Here: https://www.cs.rochester.edu/~nelson/courses/csc_173/grammars/parsing.html in chapter Driver Procedure, it's shown how table-drive predictive parsing works. The predict table however can ...
0
votes
1answer
47 views

Trouble understanding how to create a grammar parse tree

I'm starting an online Computer Science class called Advanced Programming Languages, and the book asks me to create a parse tree and generate a grammar from it. Here are the exact instructions: ...
2
votes
1answer
98 views

Grammar of regular languages vs. context free languages

Let $L$ be some language. What could you say about $L$'s grammar if it is a regular language, that couldn't be said if it was a context free language? For example, in case $L$ is regular, could you ...
1
vote
1answer
29 views

Minimal class of grammar required to run program

In computability we have the hierarchy of grammars "https://en.wikipedia.org/wiki/Chomsky_hierarchy". In this hierarchy we have many classes of grammar. This hierarchy has Turing machines at the top, ...
0
votes
2answers
61 views

Is the language $L=\{a^nb^n\} \cup \{aa*\}$ DCFL?

Is the language $L=\{a^nb^n\} \cup \{aa*\}$ DCFL OR CFL? The author says $L$ is CFL, but I am able to generate a Deterministic PDA for the corresponding language. I am naive in this subject and hence ...
3
votes
1answer
18 views

Deriving from a terminal word in a context free grammar

Just to make it clear. (since my book doesn't mention anything like this) Suppose we have a context free grammar $G=(V,T,P,S)$. where $T=\{a,b\}$ (The other sets doesn't really matter). Since ...
0
votes
2answers
49 views

Is C → A B C | A left-factorizable?

$$C \to A B C \mid A$$ Obviously has the same FIRST(C) for the both productions. But how can this be left-factorised? Tried: $$C \to A B C'$$ $$C' \to A C \mid \varepsilon$$ The FIRST sets are ...
3
votes
1answer
63 views

Proving that every derivation-tree has at most one leftmost-derivation in a context free grammar

I am trying to prove the following theorem: For every derivation-tree in a context-free grammar $G=(V,T,P,S)$ there exists at most one leftmost derivation. My partial proof by contradiction (I ...
1
vote
1answer
77 views

Cocke-Younger-Kasami (CYK) algorithem for the word $baabb$

With the context-free grammar in Chomsky's form:$$S\to BA|AC|b\\A\to AA|AB|CC|a\\B\to AS|BB|CA\\C\to AB|SS|b$$ I need to: run the CYK (Cocke-Younger-Kasami) algorithm and decide if I can ...
2
votes
1answer
45 views

Using Context free language to simulate regular expression in finite automata

Is there a minimum number of non terminal we need to use in order to simulate a finite automata with n states? When we try to convert a language accepted by NFA to context free language, do we need n ...
3
votes
1answer
43 views

Lower bound for number of nonterminals in a CFG

Let's say we have a context-free grammar for the language $a\mbox{*}b\mbox{*}c\mbox{*}$. Is there a way to determine a lower bound for the number of nonterminals in this grammar? I'm pretty sure you ...
3
votes
1answer
68 views

Prove that if you can derive w from α in n steps, it's possible with n left-derivations as well

My university's automata theory book claims that the following claim can be proved by induction but it doesn't bother showing the proof. I've tried to prove it myself but I got stuck at the ...
2
votes
3answers
57 views

Why is the distinction between linear and context-free grammars useful?

The linear grammar is a grammar that's either left, right or left and right linear. The context-free grammar can contain any kind of productions of non-terminals and terminals. All linear grammars ...
0
votes
2answers
90 views

Context-free grammar for“not-at-all” palindromes

I need to bulid a context-free grammar for $\qquad \mathscr{L_4}=\{w\in\{a,b,c\}^* \mid w\text{ is not palindrome at all}\}$ Not palindrom at all: We will say that a word $w$ is not palindrome at ...
-1
votes
1answer
27 views

Unambiguous CFG that generates regular language according to Pumping Lemma?

The pumping lemma for regular languages states: Specifically, the pumping lemma says that for any regular language L there exists a constant p such that any word w in L with length at least p can ...
-1
votes
1answer
27 views

Tools or techniques for studying the language a CFG produces? [duplicate]

When developing a CFG, I find that one can be confused about whether the grammar is correct, i.e. whether it recognizes only the required strings and not other strings. But this can be hard to see? ...
0
votes
1answer
19 views

How to convert improper CFG to weakly equivalent one?

In wikipedia there's the definition for "Proper CFG". A context-free grammar is said to be proper, if it has $$\text{no unreachable symbols}: \forall N \in V: \exists \alpha,\beta > \in ...
0
votes
2answers
51 views

Ambiguity vs. context-sensitivity

It is said that attributes supply some semantic information to the grammar. Meantime, the same attributes let you to resolve ambiguities. Text books agree that it is worth haveing a CF grammar which ...
-2
votes
2answers
53 views

Analysing a context-free grammar

Let: $$S \to AC \mid BC\\ A \to aAb \mid aA \mid a\\ B \to aBb \mid Bb \mid b\\ C \to Cc \mid c$$ I need to find if: the word $aabbbcc $ is in the grammer, and if so to write a very left series, ...
1
vote
1answer
26 views

Duplicating the quotation marks in in the quotation-mark enclosed strings

There is such a grammar string_literal ::= " { graphic_character } " The double-quotes that you see must appear in the user program and curly braces mean "any ...
0
votes
1answer
41 views

Where can I find a reasonable NLP CFG or CSG for English?

I'm looking to do natural language parsing and looking for how the CFG (or CSG) should be defined for English. Surely one'd expect to find one from the internet already, but do you know where? It ...
2
votes
0answers
18 views

Determine if two LR(1) action/goto tables always produce the same derivation

I am experimenting with implementing minimal LR(1) algorithms/techniques, but I find it very difficult to verify the correctness of what I've implemented. Is there a fast algorithm to determine if ...
4
votes
2answers
56 views

Anatomy of a production rule

Production is said to be of the form $u \to v$. I want to know if you distinguish $u$ from $v$ giving them some distinguishing names, like LHS/RHS or something alike.
0
votes
0answers
25 views

Growing context-sensitive grammars with context-free rules

Has anyone ever considered the class of languages $X$ generated by growing context-sensitive productions which are described by context-free rules? In particular, I wonder if there is a NP-complete ...
0
votes
1answer
22 views

Is it “valid” for semantic functions to query outside of the grammar in attribute grammars?

Is it valid (in the sense of formal grammars or formal language theory) to refer to outside of the grammar in attribute grammars? What I mean is that since attribute grammars can contain semantic ...
0
votes
0answers
18 views

What semantical is there in attribute grammars?

I've been reading about attribute grammars since I'm trying to extend CFGs to semantics. What I'm finding difficult to grasp is the use of the word "semantics" in the context of attribute grammars. ...
-1
votes
1answer
20 views

Context-free grammar for “member of”/set membership?

I'm wondering whether context-free grammars (or what else) can be used to implement "member of" structures, which are structures for describing that something is a member of something. E.g. I want to ...
-2
votes
1answer
43 views

How should I show that a grammar is not LL(1) and convert grammar to LL(1)

I'm trying to find the ambiguity in this grammar so I can remove it and convert it to LL(1), however for the life of me, I can't find the ambiguity. Moreover, I think there is cycle between X and Y ...
6
votes
0answers
47 views

Is THEADS the same as FIRST?

I'm reading the paper "A Practical General Method for Constructing LR(k) Parsers" by David Pager, and it contains the following paragraph: We will first of all briefly review the LR(1) parsing and ...
1
vote
0answers
32 views

Parsing based on logical connectives and quantifiers?

What techniques exist for parsing sentences based on logical connectives and quantifiers? That is, for parsing sentences that are structured "around" logical connectives and quantifiers. E.g. [A] ...
0
votes
1answer
40 views

What exactly is the LL(k) grammar condition?

I have a bit of trouble understanding the definition of LL(k) grammars. Here it's defined as: for every pair of production rules $A\rightarrow α$ and $A \rightarrow β$ the following ...
3
votes
3answers
125 views

Is the language $a^i b^j c^k$ with $i+j > k$ context-free?

I am learning about Context Free Grammars and currently stuck on the following question. Is the following language context-free? If not, then how can we prove it using Pumping Lemma? $\qquad ...
4
votes
2answers
141 views

Figuring out the language of a non-linear CFG

I have the CFG G with the following production rules: $$ S \to aSaS \mid b $$ Is it possible to find $L(G)$? I have no idea how describe it by any pattern. I use grammophone to check example words, ...
1
vote
1answer
57 views

Show that the following construction is not a correct proof for Context Free Grammars

Give a counterexample to show that the following constructions are not correct proofs for the star operation: Given a CFG $G = (V,Σ,R,S)$, add the new rule i) $ S → SS$ or ii) $S → SS|ε$. ...