# Topic 1: Formal Languages and Formal Grammar - Patience U. Usip

**Channel:** Patience Usoro Usip (Prof.)
**Source:** https://www.youtube.com/watch?v=lXDYHE4RnC4
**Transcript page:** https://www.withtranscript.ai/video/lXDYHE4RnC4

## Chapters

- 0:18 — Course Introduction and Learning Outcomes
- 1:00 — Formal Language and Set Representation
- 3:07 — Relations and String Operations
- 5:44 — Defining Formal Grammar Components
- 9:09 — Chomsky Grammar Types and Activity

## Transcript

**[0:18]:** 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 able to 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

**[1:00]:** 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 viewed as 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 starting with 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 on and then comes the right brace it can also be seen as a symbol d equals 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

**[2:56]:** can see that a set can be finite or infinity

**[3:07]:** 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 the set of other base relations can be represented in in various ways considering

**[3:48]:** 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 partitions so 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

**[4:43]:** where a string such as a can be concatenated with another string b to derive a new string a b

**[5:01]:** class activity

**[5:05]:** 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

**[5:44]:** 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 sentences a 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

**[6:47]:** well contains formula formally 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 of n 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

**[7:50]:** so

**[7:55]:** 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 that of 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 has the 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

**[9:09]:** our second activity

**[9:15]:** 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 a super 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 continue with your video

**[10:13]:** please visit the course page always as announcement will be posted there see you in our next class

**[10:48]:** you
