Is a null language a regular language

Regular grammar

In this post you will find all the important information about Regular grammar in the theoretical computer science. It starts with the Definition of formal grammar of type 3 and their Production rules. This is followed by a detailed one "Regular grammar example"by explaining evidence of regular language. At the end you will get the Connection with finite automata explained.

If you like the subject though short and compact want to have explained, just have a look at our Video at. There you will get the regular grammar explained simply and quickly using examples!

  • Regular grammar - general
    in the text
  • in the text
  • Regular Grammars and Regular Languages
    in the text
  • Relation of deterministic finite automaton
    in the text

Regular grammar - general

The regular grammar represents a type 3 grammar of the Chomsky hierarchy and creates regular languages. It is a 4-tuple, consisting of the set of terminal symbols, non-terminals and productions, as well as a start symbol.

definition

The grammar is generated using this 4-tuple:

N is the one Set of nonterminals or variables and are designated with capital letters.

T is the Set of terminal symbols in lower case.

S. is this Start symbol and contained in N as a variable.

P. is after all that Set of production rules.

The definition thus describes, on the one hand, the basic elements of the language, i.e. terminal symbols that stand for key words in programming languages, for example. From these, sentences can then be put together that are based on production rules or construction rules.

Production rules

Regular grammars consist of highly restricted rules of the following form:

and

A distinction is made depending on whether the nonterminal is on either on the far left, or on the far right. Depending on the shape, a distinction is therefore made between right-linear and left-linear.

There can only ever be one variable on the respective page.

This is replaced by one of three options on the respective page:

  • By - so nothing;
  • by a terminal symbol, a character from the alphabet of the language;
  • or by a terminal symbol followed by a non-terminal.

Right linear:


Left linear:


The rule here is that left-linear and right-linear grammars are equivalent, which means that for every left-linear grammar there is a right-linear grammar that generate the same language and vice versa.

Regular Grammars and Regular Languages

Regular grammars create regular languages, so there is always at least one regular grammar for every regular language.

For a better understanding we consider the following language as a "regular grammar example":


It contains all words that begin with one to n zeros and end with zero or an even number of ones.
If this language can be reduced to a regular grammar as just described, then it is regular.

Regular grammar example

It starts with the start symbol S. At first the attempt is made to form the smallest possible word. That would just be zero.

With the first production rule “S is converted into zero” you get exactly this word.

But you need a way to generate more than one 0. This can be done by simply adding the start symbol again to the zero:

After a zero is created, you are back in S and can thus create as many arbitrary zeros as you like. The next step is to either end the word or start with the ones. You can easily expand the production rule:

S is converted to zero S or 1 S or epsilon.

But Attention! With this rule one can use the empty word produce. Or one that starts directly with a 1: . Neither can happen in this language. Therefore, a distinction must be made between the part of the word that contains zeros and the rest. For that you need another variable.

This rule can be used to create many zeros, but at least one must be created before moving on to the next part of the word in B. From B you either end with epsilon or create ones.

If the word has ones, there must be an even number of them. This is achieved with a loop:


You get from B with a 1 to C and from there with another 1 back to B. The production rules now generate the language described.



Word problem

You can now also use them to check whether a word is contained in the language. The test is carried out with "0" "0"



One chooses from off first and then go directly with you in the final state. So the word is contained in the language.

What about "0" "1"? It starts at S and then goes from 0 to B.

From here a 1 is generated and you end up in C.

Since you are not in a final state, “0” “1” is not included in the language.

Relation of deterministic finite automaton

On the one hand, there is a deterministic automaton for every regular grammar. This is created by a nondeterministic finite automaton, in which a state is created from the nonterminal symbols and, in addition, a transition is created from every construction rule. The nondeterministic automaton can then in adeterministic finite automata being transformed.

In return, there is of course a regular grammar in every deterministic finite automaton.

In general: Any language that finite automata accept is generated by a regular grammar.

You can find out how you can convert these into finite automata in our video regular languages.