Grammars and regular expressions.

In summary, the conversation discusses finding a sentence in a language generated by G to show its ambiguity and providing two different parse trees for it. It also mentions describing the language with a regular expression.
  • #1
JamesBwoii
74
0
Hi, I'm struggling with a question about a grammar, since I haven't done them for a few months and have forgotten how they work.

View attachment 4381

a.) Let L be the language generated by G. Find a sentence a of L which is composed of three terminal symbols and that shows that G is ambiguous. Show two different parse trees for a.

b.) Describe L with a regular expression.Thanks :D
 

Attachments

  • CiHgsEk.png
    CiHgsEk.png
    2.3 KB · Views: 56
Technology news on Phys.org
  • #2
a.) A sentence a of L which is composed of three terminal symbols and that shows that G is ambiguous could be "aba". Two different parse trees for this sentence could be: Parse Tree 1: a / \ a bParse Tree 2: a | b / \ a ab.) The regular expression for L could be (a|b)*a(a|b)*
 

Related to Grammars and regular expressions.

What is a grammar and what is its purpose?

A grammar is a set of rules that define the structure and composition of a language. It is used to describe the syntax and semantics of a language, allowing for the creation and interpretation of sentences and phrases.

What are the different types of grammars?

There are several types of grammars, including regular grammars, context-free grammars, context-sensitive grammars, and unrestricted grammars. Each type has its own set of rules and restrictions, with regular grammars being the most basic and unrestricted grammars being the most complex.

What is a regular expression and how is it related to grammars?

A regular expression is a sequence of characters that defines a search pattern. It is used to match and manipulate strings of text. Regular expressions are closely related to grammars as they can be used to define patterns that are recognized by regular grammars.

What are some common applications of grammars and regular expressions?

Grammars and regular expressions are used in a variety of applications, including natural language processing, computer programming, and data validation. They are also commonly used in search algorithms, text editing programs, and database queries.

Are there any limitations to using grammars and regular expressions?

While grammars and regular expressions are powerful tools, they do have some limitations. For example, they may not be able to handle complex or ambiguous language structures, and they may not be efficient for processing large amounts of data. Additionally, regular expressions can be difficult to understand and maintain, making them prone to errors if not used carefully.

Similar threads

MHB What Language Does This Specific Grammar Produce?
    • Programming and Computer Science
Replies
1
Views
1K
MHB Exploring Regular Grammars & $\phi,\phi'$ Meaning
    • Set Theory, Logic, Probability, Statistics
Replies
24
Views
4K
MHB Exploring the Complexity of Satisfiable Boolean Expressions
    • Programming and Computer Science
Replies
1
Views
1K
Prove that this language is not regular (using Pumping Lemma)
    • Engineering and Comp Sci Homework Help
Replies
1
Views
1K
MHB Designing NFA & DFA for (1001 + 110 + 11)* Language
    • Programming and Computer Science
Replies
6
Views
3K
MHB Proving a language is regular.
    • Set Theory, Logic, Probability, Statistics
Replies
4
Views
1K
How Do You Construct a Parse Tree for the Expression (a, (a, a))?
    • Engineering and Comp Sci Homework Help
Replies
4
Views
1K
I Dot product of two vector operators in unusual coordinates
    • Quantum Physics
Replies
14
Views
1K
Which gene expressions start to happen in an embryo
    • Biology and Medical
Replies
1
Views
1K
Understanding Ambiguity in If-Else Grammars: An Explanation and Analysis
    • Engineering and Comp Sci Homework Help
Replies
12
Views
2K

Hot Threads

Recent Insights

Back
Top