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: 83
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)*
 

FAQ: 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?
Replies
1
Views
1K
MHB Exploring the Complexity of Satisfiable Boolean Expressions
Replies
1
Views
2K
MHB Exploring Regular Grammars & $\phi,\phi'$ Meaning
Replies
24
Views
4K
MHB Is the language ${L}_{n}$ regular?
Replies
4
Views
2K
Understanding Ambiguity in If-Else Grammars: An Explanation and Analysis
Replies
12
Views
2K
Are These Computer Science Languages Regular?
Replies
1
Views
2K
Understanding Grammar #2: Ambiguity, Elimination, and Boolean Expressions
Replies
2
Views
2K
MHB Looking for a serie solution for a nonlinear ODE system
Replies
1
Views
2K
Direct and alternating current, a personal approach to understand them
Replies
1
Views
475
MHB Ackermann's function is μ-recursive
Replies
11
Views
4K

Hot Threads

Recent Insights

Back
Top