At first:
Σ means language characters. in your language Σ = {a, b}^ means null characters (theoretically, ^ not a member of any language character)ε means an empty string (theoretically, ε can be a member of some language)
The symbol ^ means nothing, but we use it only for a theoretical purpose, for example, the symbol ∞ infinity, which we use in mathematics (indeed, there is no number ∞ , but we use it for understanding in order to prove some theorems) similarly ^ is not that other than how we use it.
this item is not written in any book, I write it to explain / to understand the point of view. The topic is more relevant to theoretical and mathematics, and I'm from computer science.
As you say, your grammar is L = {a m b n | m != n} L = {a m b n | m != n} . Suppose the following actions are performed:
At first:
S
This means: (a very rare book can use Σ in grammar rules)
S
I replaced Σ with characters of language a | b a | b ( a , b ).
This grammar can generate a string of equal numbers of characters a and character b ( a n b n ). How can it generate a n b n ? The following is an example output:
S ---> aSb ---> aAb ---> aaAb ---> aabb ^ ^ ^ ^ rule-1 S-->A A--> aA A --> b
But these types of strings are impossible in the language L, because m! = N.
Second:
For the same reason, production rules S --> aSb | aA | bB S --> aSb | aA | bB S --> aSb | aA | bB also not correct grammar if A --> aA | Σ A --> aA | Σ or B --> bB | Σ B --> bB | Σ are in the grammar.
I think in the second grammar you mean:
S --> aSb | aA | bB A --> aA | ^ B --> bB | ^
Then this is the correct grammar for the language L = {a m b n | m != n} L = {a m b n | m != n} . Since usage:
S --> aSb
you can only generate equal numbers a ' and b , and replacing S with aA or bB , you make a conditional form in which there are unequal numbers of characters a and b that cannot be converted back to create a string of type a n b n . (since a does not generate b and b does not generate a ).
Third:
But usually we write grammar rules, for example:
S
Both forms are equivalent (generate the same language L = {a m b n | m != n} ), because as soon as you convert S to a or b , you must create at least one a or b (or more), respectively, and, therefore, the restriction m! = n holds.
Remember, it checks to see if two grammars are equivalent or not an insoluble problem . We cannot prove this using an algorithm (but logically, it works because we have a better brain than a processor: P :)).
Fourth:
In the end, I would also like to add, Grammar:
S
does not create L = {a m b n | m != n} L = {a m b n | m != n} because we can generate a n b n , for example:
S ---> aSb ---> aAb ---> ab ^ A --> ^
Grammar in formal languages
Any class of formal languages can be represented by a formal grammar consisting of four tuples (S, V, Σ, P) . (note that grammar or automata are finite representations. The weather language is finite or infinite: check numbers one and two ).
Σ : finite set of language characters.
In grammar, we usually call this a finite set of terminals (as opposed to V variables). Language characters or terminals is a thing with the help of which language strings (sentences) are built. In your example, the set of terminals Σ is {a, b} . In natural language, you can correlate terminals with a dictionary or dictionary.
Natural language means we speak Hindi, English
V : A finite set of non-terminals.
Non-terminal or say 'variable' should always be involved in grammar rules. (otherwise, the variable is calculated in useless variables, that is, a variable that does not output terminals or nothing).
See "The ultimate goal of grammar is to create language strings in the correct form, therefore, each variable should be useful in some way.
In natural language, you can map the set variable to Noun / Verbs / Tens, which defined a specific semantic property of the language (for example, Verb means "food / dream", "Noun" means "he / she / Xiy, etc."). Note In some books, you can find V ∩ Σ = ∅ , which means that the variables are not terminals.
S : Run the variable. ( S ∈ V )
S is a special variable symbol called the "Start Symbol". We can only consider a string in the grammar language L (G) if it can be deduced from the initial variable S If a string cannot be obtained from S (even if it consists of Σ language characters), then the string will not be considered in the grammar language (in fact, this string refers to the "complement language" L (G), we write the complement language L ' = Σ * - L(G) , Check: "complement language in the case of a common language" )
P : final set of production rules.
The manufacturing rules determine the substitution rules in the range from α --> β , which means that when deriving a line from S from the grammar rules at any time, α (lhs) can be replaced by β (rhs). similar to a noun that can replace it, she or Xiy, and the verb can be replaced by food, sleep, etc. in natural language.
Production rules determine the rules for the formation of language sentences. A formal language is similar to a natural language that has a pattern that can definitely take place in a certain form — we call syntax in a programming language. And because of this grammar ability, using a grammar to check syntax is called parse).
Note In α --> β , α and β both of them consist of language symbols and terminals (VU Σ)* with the restriction that in α there must be at least one variable. (since we can only replace the string containing the variable with the rule rule. the terminal cannot replace another terminal, or we can say that the sentence cannot be replaced by another sentence)
Remember: there are two Sentential Forms and Sentence in a line:
Sentence: if all characters are terminals (the sentence can be either in L (G) or in the complement language L ' = Σ * - L )Sentential: if any character is variable (not a language string, but an output string)
From @MAV (thanks !!):
To introduce the grammar of the above language L = {a m b n | m != n} L = {a m b n | m != n} , 4-tuples:
V = {S, A, B}
Σ = {a, b}
P = {S --> aSb | A | B, A --> aA | a, B --> bB | a}
S = S
note: I usually use P rules for P rotation rules, your book can use R for R ules
Terminology uses in the theory of formal languages and automates
- Capital letters are used for variables, for example. S, A, B in the construction of grammar.
- A lowercase letter is used for terminals (language characters), for example
a , b . (some temporary numbers are used, such as 0 , 1 Also ^ is an empty character). - Small letters form the last use for the terminal string
z , y , w , x (for example, you can find these notations in the pumping lemma, characters are used for a language string or substring). α, β, γ for Sentential forms .Σ for language characters.Γ for an input or output character other than language characters.^ for a null, # or ☐ symbol A symbol for an empty symbol in a Turing machine and PDA ( ^ , # , ☐ are other language symbols.ε used for an empty string (can be part of a language string, for example, { } is an empty body in C , you can write while(1); or while(1){ } both valid see here I have defined a valid program with empty sentences )∅ means empty set in set theory .Φ , Ψ used for substring in conditional forms.
Note : ∅ means set is empty, ε means the string is empty, ^ means none (do not mix in theory, everything is different in semantics)
There are no rules that I know about symbolic notation, but they are usually used by the terminology that can be found in most standard books that I observed while studying.
Next post: Tips for writing a free context grammar