100% satisfaction guarantee Immediately available after payment Both online and in PDF No strings attached
logo-home
Previously searched by you
Previously searched by you
logo
Lecture Notes on Grammars (COMP11212) £3.49   Add to cart
Quickly navigate to
Preview
  2.  
  3. The University Of Manchester (UOM)
  4.  
  5. Fundamentals of Computation (COMP11212)

Lecture notes

Lecture Notes on Grammars (COMP11212)
 5 views  0 purchase

Gain a thorough understanding of formal grammars with these comprehensive lecture notes for COMP11212. Covering context-free grammars and their role in language generation and parsing, these notes provide detailed explanations, examples, and diagrams. Ideal for students aiming to excel in the study...

[Show more]

Preview 1 out of 1  pages

Document information

  • May 30, 2024
  • 1
  • 2023/2024
  • Lecture notes
  • Francisco lobo
  • All classes

Subjects

Written for

All documents for this subject (6)

Seller

avatar-seller
jpxoi

Content preview

Grammars

Definition Definition (I UE)
*
.
18 A
context-free grammar or CFG is
given by the following : 19 : A string e is a string generated by grammar G if there is a




also called the object alphabet Sequence of strings
· an alphabet I of terminal symbol ,
.




S =
Xo = X, =... = Xn X
non-terminal symbol the elements
=
·
an
alphabet""of ,
of which are also referred to as


auxiliary characters , placeholders in some books variables, with"" called the start
of G
or
,
step the application of
,
is obtained by
such that each Xi = Vit1 one
symbol .




rules to
production a non-terminal occurring in Xi as
follows
·
a
special non-terminal Symbol Set called the start symbol
that there production rule R Y
.
Let RE
is a <
: : occur in Xi and assume
production rules of the form R where RE , non-terminal
· a
finite get of > X is a

the
Then is obtained from Zi by replacing one occurrence of R in Xi by
(EUE)
ite
and non-terminal
*

Symbol and Xe is an arbitrary string of terminal
String Y
Symbols which ,
can be read as 'R can be replaced by X:

The language generated by grammar G is the set of all strings over which are



generated by G .




I
L xample :




asbe
5 :
Example : DFA to Grammar


S xaSb xaaSbbxaaabb
i in
· = aabb

b
· S E >




anabbb
· SxaSb -aaSbbxaaaSbbbxaaaEbbb =
S W




L =
LahbIneIN] non-regular language S - aS bT

T > aT bUE


Recap W >
E


Grammars consist of a number of production rules telling us how to rewrite non-terminals into

strings of terminals and non-terminals .




A Context Free Language is one defined by a
grammar.

strict subset of the set of Context Free
The set of Regular Languages over an alphabet is a




Languages.




Parsing
Practical Example 1: Practical Example 2:


S - aBC S S > aT Ta

B > bB/E T >
aT bTlE

C > CIE a B C

S

s
· S XaBC XabBCxabaC xabacC abca = abc
b
B C
· S X aBC XaBc(XabBcCX abECa abc
=
a T A




E E A
-

I a T



E E
Practical Example 3



=ht
Se S S aas = an aea = ga




S + 55x S
S >
S + S

S -
5 xs
A SxS St S A
S > A

1 A A A A 2
A > ⑧

A = 1
0210 Context Free Languages

A >
2




Recap
A Parse Tree shows how string
a
may be generated from a
grammar .




An ambiguous where there strings that have multiple
parse trees
is
grammar one are

The benefits of buying summaries with Stuvia:

Guaranteed quality through customer reviews

Guaranteed quality through customer reviews

Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.

Quick and easy check-out

Quick and easy check-out

You can quickly pay through credit card for the summaries. There is no membership needed.

Focus on what matters

Focus on what matters

Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!

Frequently asked questions

What do I get when I buy this document?

You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.

Satisfaction guarantee: how does it work?

Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.

Who am I buying these notes from?

Stuvia is a marketplace, so you are not buying this document from us, but from seller jpxoi. Stuvia facilitates payment to the seller.

Will I be stuck with a subscription?

No, you only buy these notes for £3.49. You're not tied to anything after your purchase.

Can Stuvia be trusted?

4.6 stars on Google & Trustpilot (+1000 reviews)

79223 documents were sold in the last 30 days

Founded in 2010, the go-to place to buy revision notes and other study material for 14 years now

Start selling
£3.49
  • (0)
  Add to cart