How can I convert this grammar into a normal form?

In summary, the conversation is about a grammar that needs to be converted into a normal form. The language generated by this grammar consists of strings with only the letters a and b, with at least 1 a and no more than 2 b's in a row. The proposed solution is to use the following production rules: S --> AQ | a, A --> a, B --> b, D --> BB, R --> AQ, and Q --> AQ | DR | DA | BR | BA | b.
  • #1
z980x
1
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
  • #2
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...)
 

1. What is "Grammar into normal form"?

"Grammar into normal form" is a process in which a context-free grammar is transformed into a simpler, more structured form. This form is often used in natural language processing and is helpful in parsing and understanding sentences.

2. Why is "Grammar into normal form" important?

Converting a grammar into normal form can help eliminate ambiguity and make it easier for computer programs to understand and analyze sentences. It also allows for more efficient parsing and can improve the accuracy of natural language processing tasks.

3. What are the different types of "Grammar into normal form"?

The two main types of "Grammar into normal form" are Chomsky normal form and Greibach normal form. Chomsky normal form restricts the grammar to have productions in the form of A → BC or A → a, where A, B, and C are non-terminal symbols and a is a terminal symbol. Greibach normal form allows productions in the form of A → aB, where A is a non-terminal symbol and a is a terminal symbol.

4. How is "Grammar into normal form" different from "Grammar normalization"?

"Grammar into normal form" is a specific process that transforms a context-free grammar into a specific form, while "Grammar normalization" is a general term that refers to any process that simplifies or standardizes a grammar. Normalization may involve other transformations in addition to converting to normal form.

5. Are there any limitations to "Grammar into normal form"?

While converting a grammar into normal form can be helpful in certain applications, it is not always necessary or appropriate. Some grammars may not be able to be converted into normal form, or the resulting form may not be useful for the specific task at hand. It is important to consider the specific needs and goals of a project before deciding to convert a grammar into normal form.

Similar threads

I Congruence for Symmetric and non-Symmetric Matrices for Quadratic Form
    • Linear and Abstract Algebra
Replies
7
Views
833
I How can I find all possible Jordan forms?
    • Linear and Abstract Algebra
Replies
8
Views
1K
I Spectral theorem for Hermitian matrices-- special cases
    • Linear and Abstract Algebra
Replies
2
Views
606
Grammar to Chomsky Normal Form
    • Linear and Abstract Algebra
Replies
1
Views
2K
I Proof that if T is Hermitian, eigenvectors form an orthonormal basis
    • Linear and Abstract Algebra
Replies
3
Views
2K
How to compute the Casimir element of Lie algebra sl(2)?
    • Linear and Abstract Algebra
Replies
24
Views
2K
MHB Finding Jordan Normal Form of Matrices
    • Linear and Abstract Algebra
Replies
11
Views
4K
Ellipse Rotation: Solving with Normal Rotation Matrix
    • Linear and Abstract Algebra
Replies
12
Views
4K
Trouble building a Buck Converter
    • Electrical Engineering
Replies
14
Views
809
A About universal enveloping algebra
    • Linear and Abstract Algebra
Replies
19
Views
1K

Hot Threads

Recent Insights

Back
Top