Write a context free grammar that accepts L = a^nb^mc^k, n>m, m>=0, k>1.
Question:
Write a context free grammar that accepts L = anbmck, n>m, m>=0, k>1. The alphabet is {a,b,c}. For example, the string aaaabbccc should be accepted.
Summary:
The given language is L = anbmck such that n>m, m>=0, k>1. In this language, every string can have 0 or more ‘b’s, 2 or more ‘c’s, and the number of ‘a’s should be greater than the number of ‘b’s. The CFG and PDA of the string are explained below.
Explanation:
Context-free grammar:
A context-free grammar is a formal grammar that generates all possible patterns of strings in each formal language. Context-free grammar G is defined by four tuples such as:
G= (V, T, P, S)
Where G is grammar which consists of a set of production rules. It generates the string of a language.
T is a set of terminal symbols. Lowercase letters denote the terminal symbols.
V is a set of a non-terminal symbol. It is denoted by capital letters.
P is a set of production rules. Which replaces the non-terminals symbols (on the left side of production) in a string with other terminals of non-terminal symbols (on the right side of production)
S is the start symbol that derives the string.
Push down automata:
Push down automata is a way to implement context-free grammar in a similar way we design a DFA for a regular expression. A PDA can remember an infinite amount of information.
Basically, a PDA is:
“Finite state machine” +” A Stack”.
PDA has three components:
- An input tape.
- A control unit and
- A stack with infinite size.
Push-down automata may or may not read the input symbols, but they must read the top of the stack in every transaction.
Now in the above question we must write CFG and PDA of string.
The given language is anbmck
Let L= {acc,aabcc,aaabcc,aaabbccc…}.
CFG:
G= (V, T, P, S)
P= {S ->aABCcc
A->aA|a|λ
B->bB|b|λ
C->cC|c|λ }
V= {S, A, B, C}
T= {a, b, c, λ }
S={S}
PDA:
Q= {q0, q1, q2, q3, q4, q5}.
F= {q3, q5}.
Also, read Dijkstra’s algorithm to find the shortest path.