Grammars specify how the strings in a language can be generated. Grammars are finite representations of formal languages. In this chapter we describe four broad categories of grammars and corresponding categories of languages that the grammar categories represent. The grammar classes and respective language classes are nested by proper subset relationships, and were proposed by Chomsky as potential models for natural language. Thus, the four language (and grammar) classes are known as the Chomsky hierarchy, which is summarized in Figure ChomskyOverview. The broadest class of languages, those with the least restrictive grammars, are the unrestricted or Type 0 languages (grammars).
A grammar is specified by a 4-tuple G = (V, Σ, P, S), where V is a finite set of variables, also called non-terminal symbols; Σ is the finite alphabet of the language being represented, also called the terminal symbols of the grammar; P is a finite set of productions; and S is the start symbol and is a member of V. V and Σ have the null intersection. Each production in P takes the form α → β , where α is a string of symbols from V+Σ and | α | > 0; and where β is also a string of symbols from V+Σ, but | β | ≥ 0 (i.e., β can be the empty string, denoted by ε ). This and no other restrictions is the definition of unrestricted or type 0 grammars (Figure GrammarDefinition). A grammar G specifies the strings of a language L(G) or LG. This definition of a type 0 grammar allows α to be a string of only alphabet (terminal) symbols, but I have never seen an example of this in other textbooks. An exercise below asks you to reflect on this issue further.
Consider this simple grammar, GSimple = (V, Σ, P, S), where V = , Σ = , P = → ε, S → 0S1>, S, the start symbol, is S. There are two productions in this grammar, and we'll often use the 'or' symbol, '|', to refer to multiple productions with the same left-hand side. So, S → ε and S → 0S1 are abbreviated S → ε | 0S1. ε signifies the empty string, and is typically not part of the alphabet of a grammar (else it would be in Σ, which is not the case in this grammar). We just need some way of representing 'nothing'. In this example, there is only one variable, and the left-hand side of each production, α , is a single variable.
Beginning with only the start symbol, we can rewrite it using any of the productions that include only the start symbol on the left-hand side. This rewrite will create a string that contains variables and/or terminals. This resulting string is called a sentential form. We can then look at the sentential form created and ask whether any productions can be applied to it. A production can be applied to a sentential form if the production's left-hand side ( α ) is a sub-string of the sentential form. In case of such a match, a new sentential form is created by rewriting the matched sub-string with the matching production's right-hand side ( β ), resulting in another sentential form. And this can continue indefinitely, where a sequence of sentential forms (that are the result of s sequence of production applications) are called a derivation, where the last string in a derivation only contains terminal symbols and is a string of the language generated by the grammar (Figures SimpleGrammar and SimpleDerivationTree).
In some cases a sentential form will be reached for which no production of the grammar matches, and we call such a sentential form a dead-end and we call the attempted derivation that ends in a dead-end, a failed derivation.
Because there may be multiple productions that have left-hand sides that match a given sentential form, we can write an enumeration procedure, like depth-first or breadth first enumeration, that tries all the relevant productions, and that traces out possible derivation sequences. Enumeration as it is often taught in introductory courses is probably a procedure for enumerating or systematically visiting the nodes of an explicit graphs, but the enumeration procedure for generating a language is better thought of as enumerating an implicit graph (i.e., the “vertices”, that is sentential forms, are generated on demand). Enumerating implicit graphs is also characteristic of many AI problems.
A more complicated grammar is GComplex = (V = , Σ = , P, S), due to Hopcroft and Ullman (1979) [ 1 ] , where P is this set of productions.
4) CB → E // FYI: we could summarize productions (3) and (4) as CB → DB | E
8) AE → ε // ε is the empty string
What language could GComplex represent? Since 'a' is the only terminal symbol, it must be a language of strings that only contain 'a's. Its a fair guess that the number of a's in each string is what determines membership. Lets start seeing what strings of 'a's we are able too derive. Can we derive the string of zero a's, i.e., the empty string? No, since the start symbol is on the left-hand side of only production (1), and an 'a' is introduced right off the bat, and importantly there is no production in this grammar that removes a's once one is introduced.
Can we derive a string with exactly one 'a'? S → ACaB using production (1) → AaaCB using production (2). Indeed, production (2) is the only production that is applicable, but you should confirm that the left-hand side of production (2), 'Ca', is the only left-hand side that matches a sub-string of 'ACaB'. Again, there is no way to remove an 'a' from 'AaaCB' in order to arrive at string of a single 'a'.
Can we derive a string with exactly two a's? S → ACaB using production (1) → AaaCB using production (2) → AaaDB using production (3) → AaDaB using production (5) → ADaaB using production (5) → ACaaB using production (6) → AaaCaB using production (2), but again too many a's if two a's is our target. Again, failing to find ways of combining productions to remove a's, this path of rewrites is a dead-end. But notice that when we applied production (3) during this sequence of rewrites we had another option available to us -- we could have applied production (4) instead of (3). Lets look at that option instead. S → ACaB using production (1) → AaaCB using production (2) → AaaE using production (4). Continuing from AaaE we have AaaE → AaEa using production (7) → AEaa using production (7) → aa using production (8).
So we can derive 'aa' from GComplex. Can we derive 'aaa'? If we continue on from our previous dead-end of 'AaaCaB' above we should quickly conclude that only production (2) will apply, which will result in 'AaaaaCB'. We can't derive 'aaa', but you should confirm that we can derive 'aaaa'. Up until this point we have been hand simulating an enumeration procedure, which is probably best left to automation. As an exercise, perhaps working with a large language model such as chatGPT, code a procedure for performing an enumeration of strings generated by GComplex. But lets also step back and reason about the generation process. We have a variable 'C' that works its way from left to right through successive sentential forms, doubling 'a's as it goes. When the 'C' reaches the right end, it either changes to an 'E' using production (4) and goes left repeatedly using production (7) until it reaches the left end and 'exits' using production (8); or the 'C' at the right end becomes a 'D' using production (3), again going left repeatedly using production (5), but this time leading to a sentential form that will again result in doubling the 'a's. Rather than the language of an even number of a's, confirm your understanding that GComplex generates the strings with a positive power of 2 a's. Followup questions in our analysis include (i) why must E go left at all? (ii) Could the grammar be altered, creating an equally valid equivalent grammar, so that D doubled a's as it was going left? (iii) And if so, what other revisions would have to be made?
What is made particularly clear in this latter example of a grammar is that there is a procedure -- an iterative, looping procedure -- that underlies the design of the grammar, and though each production can be interrogated in isolation, each rule only makes sense in its relation to the entire grammar.
The formalism of a grammar includes a set of production rules, but the grammar formalism itself says little about the procedure that is used to do the derivation or enumeration of strings using these productions. So, in selecting among several productions, each of which has a left-hand side that matches a sub-string in a sentential form, we have to additionally specify a way to chose among the possibilities to advance a derivation -- e.g., choose the first rule that matches, choose a randomly selected rule among the possibility that matches, choose the matching rule with the longest left-hand side. At a larger scale, to systematically generate the strings implied by the grammar, we have to specify, for example, a breadth-first procedure for enumerating strings using the productions. We could have picked any of the many possible enumeration procedures specified in an algorithms course or an artificial intelligence course, such as depth-first enumeration or a heuristic enumeration strategy. A Markov algorithm is equivalent in representational power to an unrestricted grammar, but where the rewrite rules are ordered and a rewrite is done by the first production in the sequence with a left-hand side that matches a sentential form. That is, the procedure used for derivation is an explicit part the Markov algorithm formalism. A Markov algorithm still does not include a commitment to an enumeration strategy, but a possible project described later suggests that you consider this. BTW, the Markov of 'Markov algorithms' is the son of the Markov of 'Markov chain' fame.
If for every production α → β , | α | ≤ | β | then the grammar is said to be a non-contracting grammar since sentential forms never shrink along a derivation path. The class of non-contracting grammars define the class of languages that is identical to the languages that are defined by so-called context sensitive grammars. A context sensitive grammar has productions of the form α 1A α 2 → α 1 β α 2 where A is a variable, and α 1, α 2, and β are arbitrary strings of variables and alphabet symbols, but β cannot be the empty string. The name 'context sensitive' is because α 1 and α 2 give the context in which A can be rewritten as β .
It should be clear that every context sensitive grammar is a non-contracting grammar, but its also the case that every non-contracting grammar can be converted to a context sensitive grammar that defines the same language. [ 2 ] [ 3 ] Thus, the non-contracting grammars and the context sensitive grammars define the same class of languages. You can think of context sensitive as a normal form for non-contracting, but context sensitive is so widely used that even when talking about non-contracting grammars, we'll often use the equivalent label of context sensitive grammars (CSGs) and languages (CSLs). In any case, these grammars and languages are also referenced as Type 1.
Consider this CSG, Gabc = (, , P, S), which is due to Hopcroft and Ullman (1969) [ 4 ] , where P is the set containing the following productions.
Let's understand the procedure that is specified by this grammar. Production (1) can be used repeatedly to add a positive number of a's, as well as 'placeholders' for an equal number of b's (Bs) and c's (Cs). After applying production (1) a desired number of times, we can 'exit' with production (2), then move C's to the right with production (3), and convert the placeholders of Bs and Cs to their lower case equivalents. Confirm your understanding that the language generated by Gabc is n ≥ 1> (i.e., a positive number of a's followed by an equal number of b's and finally an equal number of c's).
Consider the grammar GComplex presented earlier. This is clearly not a CSG, since productions (4) and (8) are contracting. Does this mean that L(GComplex) is not a CSL? Not necessarily, since its possible that there is a CSG that is equivalent to GComplex. Finding an alternative and equivalent CSG for GComplex is left as an exercise.
A small point is that a grammar that is non-contracting cannot define a language that includes the empty string, since there can be no production of the form α → ε , since | ε | = 0. So technically the context sensitive languages do not include the empty string. But it’s a technicality that is easily overcome and we won’t let it necessarily prevent us from talking about languages that include ε but that are “otherwise’ context sensitive. Suppose we have a grammar G (with start symbol S) that is context sensitive and thereby excludes ε in L(G). If we want to include ε then we can create a new grammar G’ with new start symbol S’ that is identical to G, except with an additional variable S’ and two new productions, S’ → S and S’ → ε . S’ is never used otherwise. If there is something theoretical that relies on exclusion of ε then we can focus on L(G), but for purposes of allowing for ε we can use L(G’). In fact, we will relax this a bit more and allow a production of the form S → ε , so long as S is the start symbol. Note that if S appears on the right hand side of any production then this allowance will allow a rewrite to ε in intermediate sentential forms, but again that’s easily remedied if there is a theoretical point in doing so.
We will talk more about the computational implications of context sensitive languages later, but we will preview an important point now. Suppose we ask whether w is in a language L(G) – yes or no? We can construct an algorithm to answer this question for a CSL. We can enumerate the strings in the language using the CSG, and whenever we derive a string of terminals only, we check to see if its equal to w and answer ‘yes’ if so. In contrast, when a sentential form is created that is longer than w, we know that w cannot lie along that path, since the sentential forms along that path will never shrink. If all paths in the breadth first enumeration have sentential forms that are longer than w then we know that w cannot be in the language and the algorithm can answer ‘no’.
If α in each of G’s productions α → β is a single variable, then G is a context free grammar (CFG) and L(G) is a context free language (CFL). That is, regardless of the symbols in a sentential form that surround the variable on a production’s left-hand side, the variable can be rewritten to β . Context-free grammars and languages are subsets of context sensitive (or non-contracting) grammars and languages. Every context free language is also a context sensitive language, but not vice versa. Similarly, every context sensitive language is an unrestricted language, but not vice versa. Thus, because inclusion is transitive, every CFG is an unrestricted grammar and every CFL is an unrestricted language.
Consider the grammar GSimple from a previous section on unrestricted languages. GSimple is a CFG and L(GSimple) is a CFL. A similarly structured CFG is GPalindromes, over Σ = .
Note that in this example and others, we will make an allowance for the empty string ε to be in the language. Technically, the empty string is not in a CFL because that would mean that there was at least one contracting production, which is disallowed in a CSL, and thus a CFL too. Nonetheless, the exception is widely used and we'll allow the start symbol of a CSG to produce the empty string.
A derivation for 'bbaabaabb', S → ∗ ]>> bbaabaabb, using GPalindromes, is S → bSb → bbSbb → bbaSabb → bbaaSaabb → bbaabaabb.
The CFGs and CFLs are probably the most important class of grammars and languages to us, at least for practical purposes. After Chomsky’s treatment of grammars was published, Algol became the first programming language with a syntax that was defined by a context free grammar. These grammars have been used to define other programming languages, we well as markup languages, and the grammars are adapted to define parsers for these languages. You have probably seen what amounts to context free grammars in syntax diagrams for various languages.
In a derivation of a string using a CFG, every sentential form before the final string will have one of more variables in it. If at every step we rewrite the leftmost variable in the sentential form next, then the derivation is a leftmost derivation. Similarly, if we rewrite the rightmost variable at each step then the derivation is a rightmost derivation. We will typically be most concerned with leftmost derivations because of the use of CFGs in programming languages. Though we won’t interrogate the relationship deeply, suffice it to say that because a programming language syntax is largely based on CFGs and because a language translator parses a program left-to-right, leftmost derivations are more practically relevant.
In all derivations of strings in L(GPalindrome) there will always be exactly one variable (i.e., S) for every sentential form of the derivation, except the last, so that there is no difference between leftmost and rightmost derivations in that example. Let's consider a grammar for balanced parentheses instead where the productions of GBalanced are as follows.
Note that these derivations appear different, but the difference is entirely due to the order in which the variables are rewritten, and not due to something more fundamental.
A parse tree is another representation of a derivation of a string using a CFG. The root of a parse tree is the start variable of the grammar, the internal nodes each correspond to a variable to be rewritten, the children of an internal node represent the various symbols, terminal and non-terminal, in the right-hand side of the production that is used to rewrite the variable representing the parent, and the leaves throughout the parse tree are the characters in a string of the language. The derived string can be written by doing a depth-first enumeration of the tree, writing leaf/terminal symbols only.
Parse trees are invariant relative to the order of variable rewrites, so that the leftmost and rightmost derivation for '(( ))( )' using GBalanced correspond to the same parse tree.
A grammar is ambiguous if there are two or more leftmost derivations for at least one string in the language generated by the grammar. Alternatively, we could say that if there are two or more rightmost derivations, or two or more distinct parse trees, for a string in the language then the generating grammar is ambiguous. These three definitions of ambiguity are equivalent. Consider a CFG, GExp = (V, Σ, P, S), for simplified arithmetic expressions, where V = , Σ = , the start symbol is Exp, and P equals the set containing these productions:
Exp → Exp + Exp
Exp → Exp * Exp
This grammar is ambiguous since there are two distinct leftmost derivations for the string id + id * id. There are two distinct parse trees for this string as well. You can confirm that there are two distinct rightmost derivations too. Can you find other strings in L(GExp) that have more than one leftmost (rightmost) derivation and more than one parse tree?
Ambiguity of context-free grammars is particularly important because the syntax of so many programming and markup languages are specified by context-free grammars. As an interpreter or compiler processes a program or document, it should know precisely what to do in response to each lexical item that is encountered in the program/document, and an ambiguous grammar can be problematic in guiding the interpreter on the right course of action (e.g., on what micro-instructions should be executed or written as the higher level program is being processed). Its possible to add decision rules on what to do that lie outside the grammar, but removing the ambiguity in the grammar itself is an elegant option. The grammar for arithmetic expressions is the classic educational example of revising an ambiguous grammar to remove ambiguity.
It would be nice if there was a general algorithm that accepted an arbitrary ambiguous grammar and created an unambiguous grammar that generated the same language as the input grammar. Alas, no such algorithm exists. There is not even an algorithm that identifies an arbitrary input grammar as ambiguous or not! The picture is not that dismal however since in practice there are rules of thumb for disambiguating a grammar based on ‘domain’ knowledge. Programming language constructs are one kind of domain knowledge that can guide and constrain disambiguation, as in the case of the arithmetic expression example, where the domain knowledge is the constraints provided by precedence conventions, with identifiers and parenthesized expressions having the highest precedence, addition/subtraction having the lowest, with multiplication/division in between. In the case of GExp a variation we'll call GOpPrec = (V, Σ, P, S) generates the same language (i.e., L(GExp) = L(GOpPrec)), but is not ambiguous. For GOpPrec, V = , Σ = , the start symbol is Exp, and P equals the set containing these productions:
Factor → id | (Exp)
Term → Factor | Term * Factor
Exp → Term | Exp + Term
The grammar GBalanced is ambiguous because there is more than one way to derive '(( ))( )' and other strings by alternatively using production B → ( ) and B → ε. Notice that in the parse tree, ε is shown as a leaf, but is not considered an explicit symbol in the final string.
We will return to this grammar when we talk more about the relevance of CFLs to programming languages. Consider another example of an ambiguous grammar, GBalanced, from above. Can you see why this grammar is ambiguous? Consider the string that we have already addressed, '(( ))( )'. There are at least two leftmost derivations for this string. We previously only looked at one, which is repeated here: B → BB → (B)B → (( ))B → (( ))( ). This derivation uses the production, B → ( ), to transition from the third to the fourth sentential form. But consider this leftmost derivation which uses the production B → ε: B → BB → (B)B → ((B))B → (( ))B → (( ))( ). Are there any other leftmost derivations for the same string? Naturally, if there are distinct leftmost derivations then there are distinct rightmost derivations and distinct parse trees too.
In the case of this last example of ambiguity, there is a domain independent strategy for removing the source of ambiguity, while still retaining ε as a member of the language. We create a new grammar, GBalanced', by introducing a new start variable, B', and two productions, B' → B | ε, and removing the production B → ε. Note that ε is still in the language and that L(GBalanced') = L(GBalanced), but there is now only one leftmost derivation of '(( ))( )' and other strings as well. This domain independent strategy can be applied in any similar circumstance to remove the same form of ambiguity.
If all grammars that generate a language are ambiguous then the language is inherently ambiguous. There is no algorithm in the general case that can identify whether a language is inherently ambiguous or not, but clearly if an unambiguous grammar that generates the language is identified then the language is not inherently ambiguous.
Remember that ambiguity is a property of grammars, and inherent ambiguity is a property of languages.
There are two normal forms for context free grammars that have been used for practical and theoretical purposes. Any CFL that excludes ε can be expressed by a grammar in both normal forms.
Chomsky normal form (or CNF, not to be confused with conjunctive normal form in logic) has productions of the form X → YZ or X → x, where X, Y, and Z are variables and x is a terminal. Greibach normal form (or GNF) has productions of the form X → xβ, where X is a variable, x is a terminal, and β is a (possibly empty) string of variables only.
There are algorithms for translating an arbitrary CFG into an equivalent CFG in CNF and into an equivalent CFG in GNF. The conversion to CNF is the easiest. For example, if we want to find a CNF that is equivalent to Gsimplelogic, with productions S → ~S ∣ [S ⊃ S] ∣ p ∣ q then first (1) replace all terminals with terminal specific variables when the right hand side (rhs) is larger than 1 terminal:
and (2) then accumulate variables in the righthand side of length greater than 2
There are identifiable patterns in CFLs that are useful to know, for purposes of theory at least. An important such pattern is given by the Pumping Lemma (PL) for CFLs. The PL says that for any CFL there is a length threshold. If a string is equal to or larger than that threshold, call it n, then the string, w can be written as uvxyz and sub-strings v and y can be repeated indefinitely and the resulting string will be in the language too. Sub-strings v and y can be omitted as well, signified by v 0 and y 0 , and the resulting string will still be in the language. The lemma can be expressed with quantifiers as follows. If L is a CFL then
“∃n (∀w∈L, |w| ≥ n” says that there is a threshold n such that for all sufficiently long strings in the language; “(∃uvxyz = w, |vxy| ≤ n, |vy| ≥ 1” says that z can be rewritten in terms of 5 sub-strings, the central three are less or equal to the threshold (i.e., they are sufficiently close), and v and y together consist of at least one character between them.
“(∀i≥0 uv i xy i z ∈ L)))” says that we can repeat v and y zero or more times and the resulting string will still be in the language.
The reasoning behind this construction stems from considering the parse tree for a sufficiently long string generated by a Chomsky Normal Form grammar, which can represent any CFL. If the CNF grammar has k variables, then let the threshold of n be 2 k . As the accompanying figures illustrate for the case of a string of at least n in length, at least one variable must appear at least twice along a path of the parse tree. It is the identification of this necessary repeating variable that is basis of being able to repeat or ‘pump’ sub-strings with the expectation that the result will be in the language. If the pumping lemma seems somewhat convoluted, give it time and it may seem elegant, and maybe does already.
The Pumping Lemma can be used to show by contradiction that certain languages are not CFLs. Our job is to find a sufficiently long string w that is undeniably in the language of interest and then to show that there no no way of partitioning the string into uvxyz under the PL's constraints such that the result of pumping v and y some number of times results in a string that is also in the language. The outline of a proof that L is not a CFL follows the lemma as expressed with quantifiers above.
Example: Show that L = is not a CFL.
Step 1: Let n be the pumping lemma constant. Select w = a m where m be the first prime greater than or equal to n.
Step 2: w = a m = uvxyz, where |vxy| ≤ n and |vy| ≥ 1, though the former constraint is not used in this example
Step 3: Without lose of generality assume v has j a's and y has k a's (j+k ≥ 1), so v=a j , y = a k , uxz = a m-(j+k)
Now consider successive values if i (through pumping)
|w| = |uvxyz| = j + k + m – (j + k) = m
|uv 2 xy 2 z| = 2j + 2k + m – (j+k) = m + j + k
|uv 3 xy 3 z| = 3j + 3k + m – (j+k) = m + 2j + 2k
|uv m+1 xy m+1 z| = (m+1)j + (m+1)k + m – (j+k)
= m (1 + j + k) can’t be prime, so a m (1 + j + k) not in language, which violates the PL condition that (∀i≥0 uv i xy i z ∈ L) if L is a CFL.
In step 3 it can be the case that we have to consider a number of different cases in order to show a contradiction across all i.
Example: Show that is not CFL
Step 1: Let n be the pumping lemma constant. Let w = a n b n+2 c n+4 . w is certainly long enough whatever the particular value of n.
Step 2: Let w = a n b n+2 c n+4 = uvxyz ; |vx| >= 1; |vxy|
Step 3: Case of v, y all a’s and/or b’s: pump, then more a’s than b’s or b’s than c’s
Step 3: Case of v some number of a’s; y some number of c’s – can’t happen, violates constraint that |vxy|
Step 3: Case of vy all c’s. Consider uv 0 xy 0 z, then more b’s than c’s or equal number of b’s and c’s
Finally, regular languages are a proper subset of the context free languages, and regular grammars puts a further restriction on the context free grammars. A regular grammar is a context free grammar where every production is of the form A → aB or A → a, where A and B are variables and a is a terminal. At first glance a regular grammar looks like a grammar in GNF, but where GNF allows any number of variables to follow the terminal in the right-hand side of a production, a regular grammar allows at most one. We get to applications of regular grammars and languages later when discussing the broader applications of context free languages for programming and markup language syntax.
Consider this grammar Gregular = (, , P, S>, where P is the set of productions:
You are asked to characterize the language generated by Gregular as an exercise, but clearly it is regular. Figure ParseRegular gives a parse tree for the string 1110, which is a right linear tree. Every parse tree for a string generated by a regular grammar will be right linear. For this reason regular grammars are sometimes called right linear grammars, and the languages they generate are sometimes called right linear languages in other sources. This book will use 'regular' consistently when referring to grammars and languages, however.
Every regular grammar is a context free grammar. Note that regular grammars, by definition, are in GNF. A regular grammar can be easily changed to a grammar in CNF that accepts the same language. In particular, replace each production of the form A → aB in a regular grammar with A → A'B, where A' → a is also added as a production.
Since every regular language is also a context free language, the pumping lemma for CFLs also apples to RLs, but in this latter case of a regular language, y and z are both empty. Thus, the Pumping Lemma for regular languages can be simplified to
∃n (∀w∈L, |w| ≥ n (∃uvx=w, |uv|≤n, |v|≥1(∀i≥0 uv i x ∈ L))), which is illustrated in Figure PLregular.
Let's revisit L = 0 m | m is prime>. We already know that this is not a CFL, so its obviously not an RL either, so this is just to illustrate the RL form of the Pumping Lemma. Assume L is regular, so L is accepted by a DFA with n states (aka pumping lemma constant n). Consider a string of m 0s where m is the first prime number greater than n.
0 m = 0 j 0 k 0 m-(j+k) , where u = 0 j , v = 0 k , and x = 0 m-(j+k) .
Pump v once j+2k+(m-(j+k)) = k+m
Pump v twice j+3k+(m-(j+k)) = 2k+m
Pump m times j+(m+1)k+(m-(j+k)) = mk+m = m(k+1) is not prime
0 m(k+1) not in L by definition – a contradiction
Type 0 Discussion 1: We noted in the first paragraph of this section that the definition of a grammar did not seem to overtly preclude the possibility of a production with a left-hand side of only terminal symbols (i.e., with no variables). List the implications of allowing productions with left-hand sides of only terminal symbols. As you reflect on the matter, consider discussing the issue with a large language model -- you are welcome to do so.
Type 0 Project 1: Research and discuss the relationship between Type 0 grammars and Markov Algorithms. Start by reviewing the Wikipedia site for Markov algorithm, as well as other relevant sources.
CSL Exercise 1: Give a derivation for 'aabbcc' using Gabc.
CSL Exercise 2: Give an attempted derivation for 'aabc' using Gabc. Clearly indicate deadend paths in a breadth-first enumeration of paths.
CSL Exercise 3: Find a context sensitive (non-contracting) grammar that is equivalent to GComplex -- that is, your answer should generate the same language as GComplex, but have no contracting productions. Hint: such a grammar can be found. You are welcome to use a large language model to gain insights into the process of converting GComplex to an equivalent CSG, GComplex'.
PL Exercise 1: Show = 1> is not a CFL. Note that the number of a's is j 2 , not j*2, and that the number of b's is j. That is, the number of a's is the square of the number of b's.
PL Exercise 2: Show that i#bi+1 | bi is i in binary> is not a CFL
PL Exercise 3: Show that is not a CFL.
PL Exercise 4: Can v 0 and y 0 be used in an alternative proof that L = is not a CFL? If so, how?
CFG Exercise 1: Give a context-free grammar for the language of strings over with exactly twice as many a’s as b’s. Due to Hopcroft and Ullman (1979) [ 5 ] and Hopcroft, Motwani, and Ullman (2007) [ 6 ] . Hint: you may have to consider different special cases, allowing for the a's to be positioned differently relative to the bs.
CFG Exercise 2: Give a context-free grammar for the language of . Due to Hopcroft and Ullman (1979) and Hopcroft, Motwani, and Ullman (2007).
CFG Exercise 3: Give a Chomsky Normal Form grammar (a) for L(GExp), (b) for balanced parens, (c) for palidromes over .
CFG Exercise 4: Give a Greibach Normal Form grammar (a) for L(GExp), (b) for balanced parens, (c) for palidromes over .
Type 3 Exercise 1: Give an English characterization of the language generated by Gregular. If you use a large language model, then give the prompt that you used, and the response that you received, along with any edits or corrections that you made.
Type 3 Exercise 2: Give a regular grammar that generates allowable identifiers in a fictional programming language, where the identifiers must begin with a letter, followed by any finite number of letters and digits. Special characters _ (underscore) and - (hyphen) can be used but no two of these special symbols can appear consecutively, nor can an identifier end in a special symbol.
Type 3 Exercise 3: (Due to ?) Give a regular grammar generating L =
PL Exercise 5: Show that the set of strings of balanced parentheses is not regular using the Pumping Lemma.
PL Exercise 6: Show that L = i*i | i is an integer and i ≥ 1> is not regular. I used i*i instead of i 2 for reasons of formatting.
