Home | Contact Us

C-Sharp | Java | Python | Swift | GO | WPF | Ruby | Scala | F# | JavaScript | SQL | PHP | Angular | HTML

Automata Context-free Grammar | CFG

Automata Context-free Grammar | CFG with automata tutorial, finite automata, dfa, nfa, regexp, transition diagram in automata, transition table, theory of automata, examples of dfa, minimization of dfa, non deterministic finite automata, etc.

<< Back to AUTOMATA

Context-Free Grammar (CFG)

CFG stands for context-free grammar. It is is a formal grammar which is used to generate all possible patterns of strings in a given formal language. Context-free grammar G can be defined by four tuples as:

G = (V, T, P, S)


G is the grammar, which consists of a set of the production rule. It is used to generate the string of a language.

T is the final set of a terminal symbol. It is denoted by lower case letters.

V is the final set of a non-terminal symbol. It is denoted by capital letters.

P is a set of production rules, which is used for replacing non-terminals symbols(on the left side of the production) in a string with other terminal or non-terminal symbols(on the right side of the production).

S is the start symbol which is used to derive the string. We can derive the string by repeatedly replacing a non-terminal by the right-hand side of the production until all non-terminal have been replaced by terminal symbols.

Example 1:

Construct the CFG for the language having any number of a's over the set ∑= {a}.


As we know the regular expression for the above language is

r.e. = a*   

Production rule for the Regular expression is as follows:

S → aS    rule 1
S → ε     rule 2

Now if we want to derive a string "aaaaaa", we can start with start symbols.

aaS          rule 1
aaaS         rule 1
aaaaS        rule 1
aaaaaS       rule 1
aaaaaaS      rule 1
aaaaaaε      rule 2

The r.e. = a* can generate a set of string {ε, a, aa, aaa,.....}. We can have a null string because S is a start symbol and rule 2 gives S → ε.

Example 2:

Construct a CFG for the regular expression (0+1)*


The CFG can be given by,

Production rule (P):
S → 0S | 1S
S → ε

The rules are in the combination of 0's and 1's with the start symbol. Since (0+1)* indicates {ε, 0, 1, 01, 10, 00, 11, ....}. In this set, ε is a string, so in the rule, we can set the rule S → ε.

Example 3:

Construct a CFG for a language L = {wcwR | where w € (a, b)*}.


The string that can be generated for a given language is {aacaa, bcb, abcba, bacab, abbcbba, ....}

The grammar could be:

S → aSa     rule 1
S → bSb     rule 2
S → c       rule 3

Now if we want to derive a string "abbcbba", we can start with start symbols.

S → aSa 
S → abSba       from rule 2
S → abbSbba     from rule 2
S → abbcbba     from rule 3

Thus any of this kind of string can be derived from the given production rules.

Example 4:

Construct a CFG for the language L = anb2n where n>=1.


The string that can be generated for a given language is {abb, aabbbb, aaabbbbbb....}.

The grammar could be:

S → aSbb | abb

Now if we want to derive a string "aabbbb", we can start with start symbols.

S → aSbb
S → aabbbb	

Next TopicDerivation

Related Links:

Related Links

Adjectives Ado Ai Android Angular Antonyms Apache Articles Asp Autocad Automata Aws Azure Basic Binary Bitcoin Blockchain C Cassandra Change Coa Computer Control Cpp Create Creating C-Sharp Cyber Daa Data Dbms Deletion Devops Difference Discrete Es6 Ethical Examples Features Firebase Flutter Fs Git Go Hbase History Hive Hiveql How Html Idioms Insertion Installing Ios Java Joomla Js Kafka Kali Laravel Logical Machine Matlab Matrix Mongodb Mysql One Opencv Oracle Ordering Os Pandas Php Pig Pl Postgresql Powershell Prepositions Program Python React Ruby Scala Selecting Selenium Sentence Seo Sharepoint Software Spellings Spotting Spring Sql Sqlite Sqoop Svn Swift Synonyms Talend Testng Types Uml Unity Vbnet Verbal Webdriver What Wpf