Skip to content

Lecture No. 31

Dated: 09-04-2025

The grammatical rules which involve meanings of the words are called semantics meanwhile which don't are called syntactics.
In general, the rules of a computer language are all syntactical and not semantical.
A law of grammar is just a suggestion for possible substitutions.

Terminologies

Terminals

The symbols which cannot be replaced by other symbols.

Non Terminals

The symbols that must be replaced by other things are called non terminals.

Productions

The grammatical rules are often called productions.

Context Free Grammar

It is a collection of the following

  • An alphabet1 \(\Sigma\) of letters called terminals from which the strings1 (words1 of the language1) are formed.
  • A set2 of symbols called non terminals, one of which is \(S\) which stands for "Start Here".
  • A finite set2 of productions of the form non terminal → finite string1 of terminals and/or non terminals.

Non Terminals are capitalized meanwhile terminals are not.

Context Free Language

A language generated by context free grammar is called context free language.

Example

\[\Sigma = \{a\}\]

Productions

\[S \to SS\]
\[S \to a\]
\[S \to \Lambda\]

Language Defined

\[a^*\]
\(\Lambda\) has special purpose.

It is not considered a terminal. It just means that if there's a production for a non terminal such that \(N \to \Lambda\) then \(N\) can be deleted from the string.1

Example

\[\Sigma = \{a, b\}\]

Productions

\[S \to X\]
\[S \to Y\]
\[X \to \Lambda\]
\[Y \to aY\]
\[Y \to bY\]
\[Y \to a\]
\[Y \to b\]

Language Defined

\[(a + b)^*\]

References

  1. Read more about fundamentals. ↩↩↩↩↩↩

  2. Read more about sets. ↩↩