Greibach Normal Form (GNF)
A CFG G = (V, T, P, S) is in Greibach Normal Form (GNF) if its all productions are of type A → aα, where
α ∈ V* (string of variables including null string) and a is single terminal (a ∈ T).
- Every CFG production of GNF grammar contains a single terminal (a) followed by any sequence of
non-terminals (α). i.e., A → aα - Every CFL L without null string (ε) can be generated by GNF grammar has productions are of type
A → aα, where α ∈ V* and a ∈ T. - No CNF or no GNF context free grammar generates the null string. Hence for ε-free CFG’s only we can construct an equivalent CNF or an equivalent GNF.
- In GNF context free grammar, the restrictions only on the positions, but not on length of right side of a production.
- The number of productions required to generate the x-length string from the given GNF-context free grammar is: |x|
Example: To produce a string “ab”.
Number of productions = length of the string = |ab| = 2.
The productions are: S → aB and B → b
Dear Aspirants,
Your preparation for GATE, ESE, PSUs, and AE/JE is now smarter than ever — thanks to the MADE EASY YouTube channel.
This is not just a channel, but a complete strategy for success, where you get toppers strategies, PYQ–GTQ discussions, current affairs updates, and important job-related information, all delivered by the country’s best teachers and industry experts.
If you also want to stay one step ahead in the race to success, subscribe to MADE EASY on YouTube and stay connected with us on social media.
MADE EASY — where preparation happens with confidence.
MADE EASY is a well-organized institute, complete in all aspects, and provides quality guidance for both written and personality tests. MADE EASY has produced top-ranked students in ESE, GATE, and various public sector exams. The publishing team regularly writes exam-related blogs based on conversations with the faculty, helping students prepare effectively for their exams.
