Left-linear grammar from union of 2 languages

  • Thread starter francisg3
  • Start date
  • Tags
    Union
In summary, the conversation discusses the conversion of two grammars, S1 and S2, into a left-linear grammar. The first grammar, S1, is a regular right-linear grammar which can be easily converted into a left-linear grammar. The second grammar, S2, is non-linear and the conversation suggests listing words from both grammars to find a pattern.
  • #1
francisg3
32
0
Consider the regular gramma G1 (seen below as S1) and the grammar G2 (seen below as S2). Give a left-linear grammar of L(G1) U L(G2)

S1->abA
A->baB
B->aA | bb

S2->AS2 | λ
A->aaB
B->bB | ab



I know that S1 is a regular right-linear grammar which can be changed into a left-linear grammar easily. I am having trouble with the second grammar which seems to be non-linear.

I was able to convert the first grammar into a left-grammar (seen below) however I do not know what to do with the second non-linear grammar.

S1->Aba
A->Bab
B->Aa | bb
 
Physics news on Phys.org
  • #2
Hi francisg3! :smile:

Hmm, from your first S1 I would conclude that abbabb is in L(G1).
However, it's not in your second S1...

Have you tried listing a number of words of each language?
See if there's a pattern?
 

FAQ: Left-linear grammar from union of 2 languages

1. What is a left-linear grammar?

A left-linear grammar is a type of formal grammar used in computer science and linguistics to describe the syntax of a language. It is characterized by a set of production rules that only allow for the leftmost variable in a sentence to be replaced by a terminal or non-terminal symbol.

2. What is the union of two languages?

The union of two languages is the combination of all the elements in both languages. In terms of left-linear grammars, it refers to the merging of the production rules and symbols from two different languages into one grammar. This allows for the creation of new sentences that can be generated by either of the original languages.

3. How is a left-linear grammar from the union of two languages constructed?

To construct a left-linear grammar from the union of two languages, the production rules and symbols from each language are merged together. The resulting grammar must satisfy the condition that the leftmost variable in each production rule can only be replaced by a terminal or non-terminal symbol.

4. What is the purpose of creating a left-linear grammar from the union of two languages?

The purpose of creating a left-linear grammar from the union of two languages is to combine the production rules and symbols from both languages in order to generate new sentences that can be recognized by either of the original languages. This can be helpful in language translation and natural language processing tasks.

5. Can a left-linear grammar from the union of two languages generate all possible sentences?

No, a left-linear grammar from the union of two languages can only generate sentences that can be recognized by either of the original languages. It cannot generate all possible sentences because some of the rules from the original languages may conflict with each other, making certain sentences impossible to generate.

Similar threads

Comp Sci Complexity for generating strings of length k from CNF grammar
Replies
3
Views
1K
Regex for given languages with constraints
Replies
1
Views
1K
Use set notation to define the language generated by the grammar
Replies
1
Views
5K
Writing Context Free Grammar: Sabrina, Year 10
Replies
4
Views
4K
MHB Exploring Regular Grammars & $\phi,\phi'$ Meaning
Replies
24
Views
4K
MHB Are the instances of PCP solvable?
Replies
1
Views
1K
Understanding the generic nature of linearity in Physics
Replies
2
Views
532
Describing all unique 2-tuples from a set using Set Notation
Replies
5
Views
4K
Solving Energy Levels of 2-Spin 1/2 System
Replies
2
Views
2K
Calculate Electric Potential from Non-uniform Linear Charge
Replies
20
Views
5K

Hot Threads

Recent Insights

Back
Top