Classifications of Formal Grammars (Part 1) (YouTube Video Transcript)

(00:00:00) Your YouTube transcript will appear here (00:00:06) hello everyone and welcome back (00:00:09) in the previous session we were (00:00:11) introduced to the formal grammars (00:00:13) from this session onwards we will (00:00:15) observe the classifications of it (00:00:17) so without any further ado let's get to (00:00:20) learning (00:00:21) coming to the outcome of this session (00:00:23) today we will observe the first two (00:00:26) types that is type 0 and type 1 formal (00:00:29) grammars basically in this session and (00:00:32) in the next session as well (00:00:34) we will learn how the different types of (00:00:36) formal grammars were derived (00:00:39) before diving straight to the (00:00:40) classifications let's revisit the formal (00:00:43) definition of the grammar (00:00:45) so according to norm chomsky a phrase (00:00:48) structure grammar that is a grammar (00:00:50) which has the ability to generate is (00:00:52) defined by four tuples n t (00:00:55) p and s (00:00:57) where n is a finite non-empty set of (00:01:00) non-terminals or variables (00:01:02) t is a finite non-empty set of terminals (00:01:05) or constants (00:01:06) now since n and t are two disjoint sets (00:01:10) hence n intersection t is phi (00:01:14) coming to s it is a spatial non-terminal (00:01:17) called the start symbol (00:01:19) basically the derivation of the outcome (00:01:21) that is the string of terminals is (00:01:23) initiated from this specific (00:01:25) non-terminal and the derivation is done (00:01:28) using p which is a finite set of (00:01:31) production rules of the form (00:01:33) alpha can be rewritten as beta (00:01:36) p happens to be the most essential tuple (00:01:38) of any grammar now let's move on to the (00:01:41) classifications (00:01:43) the first category is called type 0. (00:01:47) if you remember (00:01:48) in the previous session we learned that (00:01:51) the alpha and beta of a production rule (00:01:54) can be any string over n union t (00:01:57) now n union t is generally denoted using (00:02:00) v (00:02:01) therefore v clean star closure is clean (00:02:05) star closure of n union t (00:02:08) any string over n union t is basically (00:02:11) denoted by v star (00:02:13) now during the previous session we also (00:02:16) observed that non-terminals can generate (00:02:18) both non-terminals and terminals that is (00:02:21) without a non-terminal the derivation (00:02:24) process cannot progress (00:02:26) so if we become a little specific (00:02:28) alpha can be rewritten as beta should be (00:02:31) rephrased as (00:02:33) v star nv star can be rewritten as v (00:02:36) star (00:02:37) where alpha belongs to v star nv star (00:02:41) and beta belongs to v star only (00:02:45) now why we are stating it like this (00:02:47) think about it (00:02:49) v star means any string over n union t (00:02:52) that is from v star we can generate (00:02:55) epsilon that is nothing or only (00:02:58) non-terminals or only terminals or a (00:03:01) mixture of both non-terminals and (00:03:03) terminals (00:03:04) additionally in order to generate (00:03:07) something we must have at least one (00:03:10) non-terminal in the left-hand side of (00:03:12) the production rule (00:03:14) so we are enforcing at least one (00:03:16) non-terminal in the hand side of the (00:03:18) production rule placing this n in (00:03:21) between two v stars (00:03:23) consider the following example (00:03:25) say we have a type zero grammar g which (00:03:29) has defined the production rule p as (00:03:31) follows (00:03:32) lowercase a b uppercase a b lowercase c (00:03:37) d e can be rewritten as lowercase a b (00:03:40) uppercase x and lowercase c d e (00:03:44) so basically uppercase a b is deriving (00:03:47) uppercase x in association with the left (00:03:50) context that is lowercase a b (00:03:53) and the right context lowercase cde (00:03:57) by the way a mixed batch of terminals (00:03:59) and non-terminals is called sentential (00:04:02) form and clearly using uppercase (00:04:05) alphabets we specify the non-terminals (00:04:08) whereas using lowercase alphabets we (00:04:11) generally specify the terminals (00:04:13) why am i using the term generally (00:04:16) because apart from lowercase alphabets (00:04:19) terminals can also be any other symbol (00:04:22) like plus comma parenthesis etc (00:04:26) observe carefully in this particular (00:04:28) production rule (00:04:30) alpha is having a mixed batch of seven (00:04:32) elements there is five terminals and two (00:04:35) non-terminals (00:04:37) now the sentential form it is generating (00:04:39) includes lesser number of elements to be (00:04:42) specific six elements five terminals (00:04:45) lowercase a b and c d e (00:04:48) and one non-terminal that is x (00:04:51) so since here alpha can generate beta (00:04:55) which can even include lesser number of (00:04:57) elements than alpha itself (00:04:59) by the way here beta can also have more (00:05:01) elements than alpha right now we are (00:05:04) specifically talking about this (00:05:05) production rule so basically there is no (00:05:08) restriction of any kind (00:05:10) only requirement is that (00:05:13) alpha must contain at least one (00:05:15) non-terminal (00:05:16) this is why type 0 category is also (00:05:20) known as unrestricted grammar (00:05:25) the next category is called the type 1 (00:05:27) grammar (00:05:29) now we just saw type 0's production (00:05:31) structure and also learned that it has (00:05:34) got no restriction even in generating (00:05:36) sentential form having lesser number of (00:05:39) elements (00:05:40) well this is problematic in terms of (00:05:42) membership problem (00:05:44) if we want to check whether a particular (00:05:46) string of terminals can be generated (00:05:48) from a set of production rules like this (00:05:50) one (00:05:51) the number of steps for derivation will (00:05:53) be indefinite (00:05:55) we will observe the membership problem (00:05:57) later on in details (00:05:59) for now just remember that having no (00:06:02) restriction on the production rules is (00:06:05) not suitable all the time (00:06:08) so in case of type 1 the production (00:06:10) rules are of the form (00:06:12) alpha a beta can be rewritten as alpha (00:06:16) gamma beta (00:06:17) where a is a non-terminal and alpha beta (00:06:20) and gamma are any strings over n union t (00:06:24) that is these belong to v star (00:06:28) now structure wise it is as same as type (00:06:31) zero (00:06:32) let me illustrate if we compare these (00:06:36) two structures side by side (00:06:38) n is actually a in this case (00:06:41) then the left context alpha and the (00:06:43) right context beta are v star as (00:06:45) described in here (00:06:47) and since alpha beta gamma all belong to (00:06:51) v star hence v star on the right hand (00:06:54) side of the production is represented as (00:06:56) alpha gamma beta in here (00:06:59) now if these two are the same then why (00:07:02) we are calling it a different type (00:07:04) well that is because along with this (00:07:06) newly specified structure of the (00:07:08) production rule the added restriction is (00:07:12) mod of alpha a beta should be less than (00:07:15) or equal to mod of alpha gamma beta (00:07:19) that is the right hand side of the (00:07:20) production should have at least same or (00:07:23) more number of elements in it as (00:07:26) compared to the left hand side of the (00:07:27) production rule (00:07:29) and due to this restriction (00:07:31) type 1 is also called length increasing (00:07:33) grammar (00:07:35) for an instance (00:07:36) consider the grammar having the (00:07:38) production rule capital a small c (00:07:41) can be rewritten as capital b followed (00:07:44) by small b c c (00:07:47) observe (00:07:48) the left hand side of the production has (00:07:50) two elements whereas the right hand side (00:07:53) has four (00:07:54) now let me show you how this is similar (00:07:57) to the production structure if we (00:07:59) consider the formal production structure (00:08:01) we will have to modify our production a (00:08:04) bit but don't worry it will remain the (00:08:06) same (00:08:08) if we write our example production like (00:08:10) this (00:08:11) epsilon a c can be rewritten as epsilon (00:08:15) b (00:08:16) b c c (00:08:17) then these epsilons are actually the (00:08:20) left contexts (00:08:22) now since alpha belongs to v star it has (00:08:25) the liberty to generate epsilon (00:08:27) and clearly beta being the right context (00:08:31) is generating the lowercase c (00:08:34) now the non-terminal a is actually (00:08:36) generating capital b followed by small b (00:08:40) and c (00:08:41) basically (00:08:42) capital a is deriving capital b small b (00:08:46) small c (00:08:47) however it can only derive this if the (00:08:51) left context is small c (00:08:54) so context has a strong impact in here (00:08:58) this is the reason why type 1 is called (00:09:01) context sensitive grammar (00:09:05) so in this session we observed two (00:09:07) different types of formal grammars type (00:09:10) 0 or unrestricted and type 1 that is the (00:09:13) length increasing or context-sensitive (00:09:15) grammar (00:09:18) all right people that will be all for (00:09:20) this session (00:09:21) in the next session we will observe the (00:09:23) rest of the types of the formal grammars (00:09:26) so i hope to see you in the next one (00:09:28) thank you all for watching (00:09:30) [Music] (00:09:30) [Applause] (00:09:32) [Music] (00:09:41) you