Consider the language which consists of all strings with at least one character
ID: 3666908 • Letter: C
Question
Consider the language which consists of all strings with at least one character and at most ten characters such that the first character is a letter and the remaining characters may be either letters or numbers. How many strings are in this language? If you followed the construction in the proof of observation 1, you would get a grammar with very many productions.
Observation 1:
Every finite language has a grammar. To verify this observation let L = {l1, l2, . . . , lK} be any finite language. We want to construct a grammar G such that L(G) = L. Let be the set of symbols which appear in any of the strings in L. Let V consist solely of the start symbol S. Let P = {S l1, S l2, . . . , S lK}. Clearly a terminal string can be derived from S if and only if the terminal string is in L, thus L = L(G).
Find a grammar with many fewer productions which generates this language. Give an algorithm which determines if a given string is in this language.
Explanation / Answer
Proficiency in a language does not expect one to know all the sentences
of the language; rather with some limited information one should be able
to come up with all possible sentences of the language. Even in case of
programming languages, a compiler validates a program - a sentence in the
programming language - with a finite set of instructions incorporated in it.
Thus, we are interested in a finite representation of a language - that is, by
giving a finite amount of information, all the strings of a language shall be
enumerated/validated.
Now, we look at the languages for which finite representation is possible.
Given an alphabet , to start with, the languages with single string {x}
and can have finite representation, say x and , respectively. In this way,
finite languages can also be given a finite representation; say, by enumerating
all the strings. Thus, giving finite representation for infinite languages is a
nontrivial interesting problem. In this context, the operations on languages
may be helpful
the languages , {}, {a}, and all finite sets are regular.
let G=({E,+,*,(,),a} , {+,*,(,),a},p,E) where p is the set of rules
E --> E+E
E ---> E*E
E --->(E)
E----> a