How can I convert this grammar into a normal form?

  • Context: Graduate 
  • Thread starter Thread starter z980x
  • Start date Start date
  • Tags Tags
    Form Normal
Click For Summary
SUMMARY

The discussion focuses on converting a given context-free grammar into a normal form. The original grammar is defined as S → aQ | a and Q → aQ | bbS | bS | b. The user seeks assistance in transforming this grammar, which generates strings starting with at least one 'a' and containing no more than two consecutive 'b's. A proposed transformation includes new productions such as S → AQ | a and Q → AQ | DR | DA | BR | BA | b, indicating an attempt to simplify the grammar while maintaining its language characteristics.

PREREQUISITES
  • Understanding of context-free grammars
  • Familiarity with normal forms in formal language theory
  • Knowledge of production rules and their transformations
  • Basic concepts of string generation in formal languages
NEXT STEPS
  • Study Chomsky Normal Form (CNF) for grammar conversion techniques
  • Learn about Greibach Normal Form (GNF) and its applications
  • Explore algorithms for eliminating left recursion in grammars
  • Investigate parsing techniques for context-free languages
USEFUL FOR

Students of computer science, linguists studying formal languages, and software developers working on compilers or interpreters will benefit from this discussion.

z980x
Messages
1
Reaction score
0
Hi everyone,

I have a grammar to convert into a normal form, but I have no idea how to do that. And from this normal form, I have a lot of other things to do.

Could you please convert me this grammar into a normal form:

S --> aQ | a
Q --> aQ | bbS | bS | b

Thanks in advance,
 
Physics news on Phys.org
It appears that the language generated by this grammar consists of all strings of length at least 1, containing only terminal symbols a and b, such that the string starts with at least 1 a, and has no more than 2 b's in a row.

Therefore, perhaps...

S --> AQ | a

A --> a
B --> b
D --> BB

R --> AQ

Q --> AQ | DR | DA | BR | BA | b

Is that what you're after? I just kind of threw that together, so it can probably be cleaned up considerably (if it's right...)
 

Similar threads

  • Poll Poll
Why do we spend so little time learning grammar in college?
  • · Replies 142 ·
5
Replies
142
Views
7K
Undergrad How to Convert Grammar to Chomsky Normal Form?
  • · Replies 1 ·
Replies
1
Views
3K
Graduate How to Convert Given Grammar to Chomsky Normal Form?
  • · Replies 5 ·
Replies
5
Views
25K
MHB Finding Jordan Normal Form of Matrices
  • · Replies 11 ·
Replies
11
Views
5K
Undergrad How can I find all possible Jordan forms?
  • · Replies 8 ·
Replies
8
Views
2K
Undergrad Ellipse Rotation: Solving with Normal Rotation Matrix
  • · Replies 12 ·
Replies
12
Views
5K
MHB Jordan Normal Form of Unitary Transformation
  • · Replies 2 ·
Replies
2
Views
2K
Undergrad Spectral theorem for Hermitian matrices-- special cases
  • · Replies 2 ·
Replies
2
Views
3K
MHB Normal Form and Canonical Form of a Quadratic
  • · Replies 20 ·
Replies
20
Views
19K
MHB How can we prove that E/Q is a normal extension?
  • · Replies 1 ·
Replies
1
Views
2K