What logic is used to build context free grammar for L= a^m b^n; m>n

  • MHB
  • Thread starter shivajikobardan
  • Start date
  • Tags
    Build Logic
In summary, the conversation is about understanding the solution for a CFG problem. The speaker is struggling to understand how the solution was derived and is asking for guidance on problem-solving skills. The solution involves repeatedly applying rules to build strings of the form $a^nS$ and $a^{n+1}T$, and then using $T\to\varepsilon$ to produce the final string $a^{n+m+1}b^m$. This is the only way to generate strings using this grammar.
  • #1
shivajikobardan
674
54
1636741535608.png
I have the solution but I am unable to decode the solution, how did we come up here? can you tell me that?
 
Technology news on Phys.org
  • #2
Is the problem "Derive $aaab$? Then you are given an explicit derivation. Do you know the definition of a derivation in the context of grammars? What exactly is not clear?
 
  • #3
No. I understand derivation. My problem is that I am not understanding how we came up to this solution of CFG. I want that problem solving skill to learn rather than trying to memorize this. So I am asking this. There must be some patterns of questions there right? Can you guide me a bit in this question?
 
  • #4
Applying rule $S\to aS$ $n$ times where $n\ge0$ allows building strings of the form $a^nS$ from $S$. Then the only different thing to do is to apply $S\to aT$ to produce $a^{n+1}T$. After that, applying $T\to aTb$ $m$ times where $m\ge0$ produces $a^{n+1}a^mTb^m$. Finally, $T\to\varepsilon$ finishes the derivation and produces $a^{n+m+1}b^m$. These are the only strings (for some $n,m\ge0$) that one can generate using this grammar.
 

Related to What logic is used to build context free grammar for L= a^m b^n; m>n

1. What is a context-free grammar?

A context-free grammar is a set of rules that defines the structure of a formal language. It consists of a set of symbols, a set of non-terminal symbols, a start symbol, and a set of production rules. It is used to generate strings in the formal language.

2. How is context-free grammar used in building L= a^m b^n; m>n?

In order to build L= a^m b^n; m>n, we use context-free grammar to define the structure and rules for generating strings in this language. The non-terminal symbols in the grammar represent the different components of the language (a's and b's), and the production rules dictate how these symbols can be combined to form strings in the language.

3. Can you provide an example of a production rule for L= a^m b^n; m>n?

One possible production rule for this language could be S → aSb, which means that the start symbol S can be replaced by an 'a' followed by another S and then a 'b'. This rule can be repeated until the desired number of a's and b's is reached, satisfying the condition m>n.

4. How is the logic of context-free grammar related to the mathematical concept of exponentiation?

The use of exponentiation in the language L= a^m b^n; m>n is represented by the production rule S → aSb. This rule can be repeated m times, resulting in a string with m a's. Similarly, the rule S → aS can be repeated n times, resulting in a string with n b's. This reflects the mathematical concept of exponentiation, where a base is multiplied by itself a certain number of times, resulting in a number raised to a power.

5. What is the significance of the condition m>n in the language L= a^m b^n?

The condition m>n ensures that the language L= a^m b^n only generates strings where the number of a's is greater than the number of b's. This is important in maintaining the structure and meaning of the language, as the position and quantity of a's and b's can convey different information in a formal language. Without this condition, the grammar may generate strings that do not accurately represent the language.

Similar threads

  • Engineering and Comp Sci Homework Help
Replies
2
Views
914
  • Programming and Computer Science
2
Replies
57
Views
3K
  • Programming and Computer Science
Replies
4
Views
2K
  • Programming and Computer Science
Replies
1
Views
739
  • Programming and Computer Science
Replies
15
Views
2K
  • Programming and Computer Science
Replies
14
Views
3K
  • Linear and Abstract Algebra
Replies
1
Views
1K
  • Precalculus Mathematics Homework Help
Replies
17
Views
379
  • Programming and Computer Science
Replies
19
Views
2K
  • Set Theory, Logic, Probability, Statistics
Replies
21
Views
2K
Back
Top