All Questions

Filter by
Sorted by
Tagged with
1
vote
1answer
28 views

Efficiency/Redundancy in Chomsky normal form

I have a context-free grammar with the following production rules, $S$ being the start symbol: $$\begin{align*} S &\to AB \\ A &\to a \\ B &\to a\end{align*}$$ Is this in Chomsky normal ...
0
votes
1answer
38 views

Context free grammar to Chomsky's normal form

\begin{align*} S&\to AACD\\ A&\to aAb\\ C&\to aC\mid a\\ D&\to aDa\mid bdb\mid\varepsilon \end{align*} I think that this grammar is infinite so it is not possible to convert it into ...
0
votes
1answer
59 views

Reusing variable in converting grammar to Chomsky Normal Form

I'm not sure if reusing variable is allowed in CNF. For example, I have this grammar not in CNF. So I have to convert it to CNF. ...
-1
votes
1answer
139 views

Convert grammar to Greibach form

The grammar is $S \rightarrow AA|a$$A \rightarrow SA|ab$The actual question is to find an NPDA accepting the language generated by this grammar but for that i firstly need to convert it into Greibach ...
5
votes
2answers
355 views

Why is the start symbol “not allowed” on the right hand side in Chomsky normal form?

I had a question regarding CNF (Chomsky normal form) in formal language theory. I noticed that a lot of authors (including my own professor, and the Wikipedia page for CNF) frown upon or don't allow ...
-4
votes
1answer
402 views

Can any ambiguous context-free grammar be converted into Chomsky normal form? [closed]

Can an ambiguous context-free grammar be converted into Chomsky normal form? I think the answer is yes.
0
votes
1answer
284 views

Can every CFG be converted into an equivalent CFG of this form?

Question: Show that every CF grammar G = (V,T,S,P) can be converted into an equivalent CFG in which every production is of the form A → xBC or A → ϵ, where x ∈ T U {ϵ} and A,B, and C are variables. ...
2
votes
1answer
2k views

Chomsky or Greibach Normal Form?

I tried to solve this exercise: Discuss the normal forms (CNF or GNF) of a grammar with productions: $S\rightarrow BC | CB$ $B\rightarrow cB | c$ $C\rightarrow cC | \epsilon$ Same request with ...
2
votes
1answer
340 views

Proof any CFG can be converted to GNF

I studied algorithm for converting grammars to GNF and was wondering about a proof that any CFG can be converted into GNF. I found this paper - ENGELFRIET, Joost. An Elementary Proof of Double ...
0
votes
1answer
363 views

For every context-free grammar, is there an equivalent grammar in Chomsky normal form?

I thought that, for every CFG, there is an equivalent grammar in CNF. I was told this is false. Can someone explain to me why this is false and possibly provide a counter example?
7
votes
1answer
481 views

Convert PEG to BNF

Parsing expression grammars (PEGs) are unambiguous and have a superficially similar syntax to BNF, but include three important differences: The ordered choice operator ...
1
vote
1answer
311 views

Is there an algorithm for converting a CFG in Greibach Normal Form into a CFG in strong GNF?

A CFG is in strong GNF when all rewrite rules are in the following form: $A \rightarrow aA_1...A_n$ where $n \leq 2$.
0
votes
0answers
51 views

Stuck on Converting to Chomsky Normal Form,

I am supposed to be changing this to Chomsky Normal Form and then to Greibach form, but I am still having a few difficulties changing it to the first form. Here is the language: S → AA|SBBa|b A → ...
6
votes
1answer
77 views

When is ε-removal from a CFG idempotent?

For which context-free grammars is it idempotent to remove $\varepsilon$-productions? Given that there are multiple rewriting algorithms which preserve language and leave the grammar without $\...
1
vote
1answer
362 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 ...
2
votes
2answers
5k views

Why do grammars in Chomsky Normal Form have derivations of length 2n-1?

I would like to know how they obtained the expression $2n-1$ as said from the excerpt of article (p.3): The key advantage is that in Chomsky Normal Form, every derivation of a string of n letters ...
1
vote
2answers
883 views

Converting context-free grammar to Chomsky/Greibach Normal Form

Is it necessary to remove all lambda productions, unit productions and useless productions from a context free grammar(CFG) before converting to Chomsky Normal Form(CNF) or Greibach normal form (GNF). ...
2
votes
0answers
4k views

Converting CNF to GNF

I'm studying context free grammars and I can grasp how to create context free grammars given a set notation, and now to convert these context free grammars to Chomsky Normal form but I am utterly ...
0
votes
1answer
435 views

Does removal of unit production from the grammar may increase number of total production?

There are m variable in a grammar. The number of productions after removal of unit productions in the worst case is ,(Assume there are no null productions) (a) O(m) (b) O($m^2$) (c) O($k^m$) (d) O($...
-1
votes
1answer
882 views

Can we remove unit productions First Before removing Null productions?

My professor have asked me strange question , about converting from Context free grammar to chomsky normal form , Can we remove unit productions first from CFG if possible , before removing null ...
-1
votes
1answer
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, ...
-3
votes
1answer
76 views

Chomsky Normal Form of |a|<|b| [closed]

Hello Everyone I was hoping I could ask you to check to my work on this CNF, These are a pain to me and I want to make sure I'm doing it right the first time ...
3
votes
1answer
144 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?
1
vote
1answer
572 views

Converting to Chomsky normal form

Im having some problems with a qeuestion regarding converting a context free grammar to chomsky normal form. I have S -> abC | babS | de C -> aCa |b I know what to do with the case ...
0
votes
1answer
299 views

conversion of this grammar to CNF

My task is to convert the following grammar to CNF: $S \to SS \mid (S) \mid \lambda$ after removing lambda productions: $S\to SS, S\to (S), S\to(), S\to S$ after removing unit productions: $S\to ...
2
votes
1answer
45 views

Chomsky form for language of single alphabet member

I'm a bit confused as to how to represent the Chomsky form for the language L that generates all strings with the alphabet {a} My approach was ...
12
votes
3answers
10k views

The importance of normal forms like Chomsky normal form for CFGs

I understand that context-free grammars can be used to represent context-free languages.It might have ambiguities. We also have normal forms like Chomsky and Greibach normal form. I couldn't ...
1
vote
1answer
4k views

CFG to Chomsky normal form

I've read this part like 3-4 times and I'm not understanding what is going on. Let G6 be the following CFG and convert it to Chomsky normal form by using the conversion procedure just given. The ...