# Tagged Questions

The tag has no usage guidance.

78 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 ...
92 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 ...
84 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). ...
29 views

### How can I solve this Functional Dependency?

Consider R(A, B, C) with FDs F ={A→B, B→C, A→C} Prove or disprove F |= C → A There are 7 inference rules from Armstrong's Axiom. Which one is to use here?
91 views

### How to remove null-productions in a CFG?

I have the CFG $\begin{array}{lll} S &\to &BB\mid 0A0 \mid 1B1\\ A &\to &C\\ B & \to & S \mid \varepsilon\\ C & \to & S \mid A \end{array}$ And understand that when ...
227 views

### Canonical representation of programs

I'm working on some compiler software, and I'm looking for information on canonical forms for expressing software, algorithms, mathematical expressions (including predicate logic), etc. I assume ...
119 views

### Convert a CFG into CNF

I'm still new to CFG and CNF and have trouble sometimes understanding the concepts. I'm trying to convert this CFG into Chomsky Normal Form: ...
65 views

### how to compute functional dependencies and MVDs after decomposition?

Let's say we have a relation $R$ with a set of functional and multivalued dependencies $F$, and we found a dependency that violates some normal form. Then we decompose $R$ into $R_1$ and $R_2$. How to ...
115 views

85 views