Tagged Questions

Questions about formal grammars, generative descriptions of formal languages.

15 views

operator precendence grammar

According to this post http://stackoverflow.com/questions/28397767/computing-leading-and-trailing-sets-for-context-free-grammar while constructing operator precendence parser we have to create tabel ...
72 views

Why is BNF considered an unsatisfactory technique for describing a language?

I was reading the paper Fundamental Concepts in Programming Languages by C. Strachey the other day, wherein I read something that was quite strange to me. Quoting directly (with the strange part ...
24 views

Lossless Condensing, Modification, and Decondensing

Given a string $\alpha$ that is derived from context-free grammar $G$, what is an algorithm $f$ such that there exists a string $\beta$ (derived from an unrestricted grammar) where ...
36 views

Describing the language of a CFG

Let G be a CFG such that: S -> aSb | bY | Ya Y -> bY | aY | lambda Give a simple description of L(G) in English. From what I can tell from this ...
15 views

LL(1) grammar for reverse polish notation [closed]

Could anyone provide me an example of LL(1) grammar for reverse polish notation? Exactly LL(1).
43 views

Is the word problem of CFLs in NC?

Consider the membership problem for a context-free language. An instance of this problem can be described as pair $(G,w)$, where $G$ is a context-free grammar and $w$ is a string. Lets say I have a ...
35 views

The Chomsky–Schützenberger representation theorem

I've been trying to proof The Chomsky–Schützenberger, but I stuck on creating regular language from that theorem. I mean reagular language, which is intersected with Duck language. Could anyone give ...
37 views

Show that a grammar is ambigious and create an unambigious grammar

My solution is the following: To show ambigious I just made two parsetress for an example string, easy. The tricky part is to create the unambigious grammar defining the same language. Ive made an ...
33 views

How to recursively infer a word/string from a context-free grammar?

Give the recursive inference of the word $abcddd$ from the Context-free Grammar: $A\rightarrow aAd\mid B$ $B\rightarrow bBd\mid C$ $C\rightarrow cC\mid cD$ $D\rightarrow Dd\mid ϵ$ This ...
29 views

PDA to CFG equivalence (No. of states and stack symbols)

All examples of problems on converting PDA to CFG I have encountered always have a number of states EQUAL to the stack symbols. Is that always the case? I get confuse since in making productions for ...
54 views

How to use Parikh's Theorem to show language is not context free

Parikh's Theorem is quite complicated, I understand intuition of that theorem but I don't see how to use that to prove that language is not context free. I kindly ask you to show me how to do, ...
25 views

what is ( simple grammar ) in automata language? [duplicate]

what is ( simple grammar ) in automate language ? please tell me clearly . i don't understand after twice reading ... what is different between this and regular grammars ? What relation exists ...
312 views

Is language equality for linear context-free grammars decidable?

Let's consider two context-free grammars $G_1$ and $G_2$ and ask the following question: Is $L(G_1) = L(G_2)$, that is, are the two grammars equivalent? In general, this problem is undecidable. ...
472 views

Does a context-free grammar with multiple variables have a “starting” point?

So lets consider the following grammar \begin{align*} S &\to 0 \mid 0A \\ A &\to 1 \end{align*} would the string "1" be accepted by the language or must the language start with $S$?
69 views

Can every context free grammar be transformed into equivalent grammar of this form?

Show, that every context free grammar can be transformed into equivalent context free grammar ( with possible loss of $\lambda$ ) where $a \in V_t$ and $A,B,C \in V_n$ with rewriting rules of ...
21 views

Can an (extended) regular grammar have multiple nonterminals in its RHS?

Standard (right) regular grammars have three kinds of rules: A <- "" A <- "a" A <- "a" B This is OK for a theoretical point of view, but a big ...
25 views

28 views

Why descriptive power of context-free grammar is greater than regular expression?

Below is a saying from this article. Regular expressions sit just beneath context-free grammars in descriptive power: you could rewrite any regular expression into a grammar that represents the ...
24 views

How can I show context free grammars are strictly more expressive than regular expressions with an example?

I need to show a CFG can express everything that can be expressed by a regular expression, and something that cannot.. I have no idea what example is traditionally used for this.
458 views

Is it possible to build DFA for odd-length words with 1 in the middle?

$L := \{w \in \{0,1\}^* |$the length of $w$ is odd $\wedge$ 1 is in the middle of $w\}$ So the alphabet is $\{0,1\}^*$. My problem is that I can't keep track of the equality of chars before and ...
53 views

Building an undecidable T-Grammar

I am asked, "Show that these T-Grammars constitute a set of languages that are undecidable. Do this by building a T-Grammar for a Turing machine description. For a starting point you might think about ...
74 views

Show that language generated by grammar is regular

We have grammar with nonterminals $X_1,...X_n$ terminals $V_t$ and rewriting rules of form: $X_i \rightarrow a \in V_t$ $X_i \rightarrow X_jX_k, \ i \ge j , \ i > k$ How can I show that ...
33 views

Explanation of Grammar Ambiguity

Consider now the grammar G S -> (S + S) S -> (S * S) S -> a Is it ambiguous? Answer: No because there are disambiguating parentheses and so no left or right recursion. Can someone explain how the ...
84 views

What is the language generated by a given grammar

Given the grammar $s \to aSb \mid bSb \mid a \mid b$; what is the language generated by the grammar over the alphabet $\{a,b\}$? When I was solving this question I was a bit confused about ...
42 views

CFG for the language “number of a's = number of b's + 2”

How can I construct a context-free grammar for the following language? $$L = \{ w \in \{a,b\}^* : \#_a(w) = \#_b(w) + 2 \}.$$ Please help me out in this. I am not sure how to approach this ...
58 views

31 views

How do I get and/or verify a formal Grammar for a given formal Language? [duplicate]

I was given the Language $L=\left \{ a^nb^na^nb^n |n\epsilon \mathbb{N} \right \}$ and I'm supposed to find a Grammar that generates that Language. After some trying and fiddling I found one that I ...