# Questions tagged [formal-grammars]

Questions about formal grammars, generative descriptions of formal languages.

1,030 questions
Filter by
Sorted by
Tagged with
2k views

### CFG for $\{a^i b^j : 2 i<j\}$ [duplicate]

So I have a question: Give a CFG for $\{a^i b^j : 2 i<j\}$ And this is my approach: $S\to AB$ $A\to aAb\mid \varepsilon$ $B\to b \mid bB$ A confirmation, or correction, along with how you ...
141 views

### Context free grammar for {a^mb^n | m ≠ n} [duplicate]

I need to find a context-free grammar for the above expression, $a^{m}b^{n}$ for the set $L = \left\{{a, b}\right\}$, but I am having difficulty accounting for the condition $m \neq n$. This is what ...
59 views

### How i can use Mathematical induction to prove CFG production? [duplicate]

If I have production $G_n$ $S \rightarrow A_i b_i \quad$ for $1 \le i \le n$ $A_i \rightarrow a_j A_i \mid a_j\quad$ for $1 \le i$ and $i \ne j$ Prove $G_n$ is sub-productions from $2n^2 - n$ ...
32 views

### Design a CFG that generates the language { x in {a,b}* | the length of x is odd and its middle symbol is a b }

I am trying to design a context-free grammar that generates the language { x in {a,b}* | the length of x is odd and its middle symbol is a b }. This is really confusing me, I'm having trouble with ...
78 views

### Construct a grammar for the language

How can I achieve this. Write a grammar for the language consisting of strings built only of the letters a and b. The strings may have any number of these letters, but the letter combinations bab must ...
123 views

1k views

### Generating grammar for the given language

Can someone please give a couple of examples of the language and construct a grammar for the language (given below), or at least show me how I can go about it? I am looking for a context-free grammar ...
108 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 ...
432 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 ...
41 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 ...
56 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 ...
2k views

### Chomsky Normal Form-remove unit production

In the step of removing unit productions when converting a grammar to Chomsky normal form, I sometimes found that the variables may end up having the same production bodies. Is this possible? If so, ...
122 views

### Eliminate Left Recursion

The part I want to modify: B -> F | B A | A What is the correct way to remove this left recursion? I was thinking ...
265 views

### Programming Languages Grammar Ambiguity [closed]

I don't know if it is the right site to ask this. But we're studying about ambiguities of grammar. Including left most derivation and right most derivation. We are given the problem: ...
175 views

### Equivalence of some Automata & Language & NFA

I read some note about Automaton Course. i see this note, that following all is the same. but i think the L(g) is not equal to NFA and regular expression. anyone could help me with defining the ...
945 views

59 views

### How to design a formal grammar to convert EBNF description to a list of CFG production rules

I would like to write a grammar to convert EBNF description to a list of CFG production rules, instead of an algorithm. Can CFG production rules is generated from an EBNF description by a rewrite ...
17 views

408 views

### Find the Unambiguous Grammar [closed]

Consider the following grammar: S->A. A->A+A|B++. B->y Check whether grammar is Ambiguous or not? Also ,unambiguate the grammar.Now please tell me what will be the grammar after removing the ...
49 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? ...
265 views

### How to write Context-free Grammar for this language? [closed]

I am trying to teach myself how to write Context-free Grammar for different languages. I have an example language I am trying to work out and this is the answer I came up with, does it make sense? ...