Transcript
Use with ChatGPT / Claude Auto-scroll A
The instructor introduces the compiler principles course and outlines the session's learning objectives on formal languages and grammar.
i am doctor and we'll be taking you on the course cit 445 principles and techniques of compiler in today's live session we'll be considering formal language and formal grammar at the end of today's class learners will be ableto understand what language is they will be able to describe formal grammar and they will also be able to differentiate the various classes of grammar as given by noam chomsky sit back and enjoy your class thank you very
Defines formal language as a set of strings and demonstrates multiple ways of representing sets, including finite and infinite sets.
much you are welcome to the class proper on formal language in formal our intended grammar outcomes to include understanding what language is understanding from our grammar and differentiating the various types of grammar a formal language can be viewedas a programming language that consists of a set of relations or strings as collection of objects in any given domain there are specific ways of representing a set for example a set of decimal digits can be written startingwith the left braces followed by 0 1 2 3 4 up to 9 and ending with the right brace it can also be represented as a symbol d equals to a left breast followed by 0 and so onand then comes the right brace it can also be seen as a symbol dequals to the set of x such that x is a decimal digit you can also say that it is a symbol d equals to the set of x such that p of x is true from this example we
can see that a set can be finite or infinity
Covers relations, their representations (matrices, directed graphs, partitions), string concatenation, and includes a class activity on set concatenation.
we said that the set contains relations and strings by relations we mean the basic mathematical concepts used in everyday life the concept is used for comparing objects related to each other example is the binary relations which is theset of other base relations can be represented in in various ways considering
um what you have to do we can represent it as a relation matrix we can also relate represent it as a directed graph where structures like the infinite automata will come in we can also represent it as partitionsso relations can be defined on the rules of the grammar a string over an alphabet is either a letter or a sequence of letters derived so the string operations include associativity and concatenation
where a string such as a can be concatenated with another string b to derive a new string a b
class activity
first one so consider the concatenation of two sets of strings b a b and a b a what will be the resulting string after concatenation please attempt this class activity before you continue watching the video
Introduces formal grammar as a finite description of sentences and explains its tuple components: terminals, non-terminals, start symbol, and rules.
so let us continue with formal grammar by formal grammar referring to a formal method to describe a language in textual form formal grammar can be defined as a finite description of a possibly infinite set of acceptable sentencesa formal grammar is a generative device that imposes structure and the sentences of a language it consists of a finite non-empty set of rules or productions which specify the syntax of the language hence a formal grammar
well contains formulaformally stated a grammar g is equals to a tuple consisting of v t v n s and r where v t are set of terminal symbols usually placed on the terminal nodes and represented with small letters v ofn are set of non-terminal symbols placed on non-terminal nodes and represented with capital letters s as certain symbols usually placed on the root node and are affinity non-empty set of rules to combine symbols
so
known as type 2 and a regular grammar known as type 3 from this classification we can see that the number of constraints in regular grammar is more than that of context-free which is in time in turn modern thatof the context sensitive grammar in regular grammar alpha implies beta where the length of alpha is less than or equals to the length of beta an alpha is an element in the set of non-terminal symbols and beta hasthe form small letter a capital letter b or small letter a where a is an element in the set of terminal symbols and capital letter b is an element in the set of non-terminal symbols and so here comes
Discusses the Chomsky hierarchy of grammar types (regular to type 0), presents a quiz activity on subset relationships, and gives closing remarks.
our second activity
which of these options correctly represents the types of grammar according to norm chomsky option a says that type 0 grammar is a superset of type 1 which is in turn a superset of type 2 which also is asuper set of type 3.option b says that type 0 grammar is a subset of type 1 grammar which is in turn a subset of type 2 grammar which is a subset of type 3 grammar please attempt this class activity before you continuewith your video
please visit the course page always as announcement will be posted there see you in our next class
you