Answer to Question #227651 in Algorithms for kkk

Question

Question 1

A language processing system aims at compiling source programs into codes

for the computer to execute. A language can thus be defined as a set of strings. There are several known ways of specifying a language.

 

​a) Describe what a grammer is ​​​​​​

 

​b) Given a language L and grammer denoted as G1 show that aabb is in L(G1) where the the ​grammer G1 is defined as 

​1. S —›ASB

​2. S —›Ɛ

​3. A —›a

​4. B —›b

​where a,b are terminal symbols and Ɛ represents the null string.

​​​​​​​​​​​​​

​​​​​

Answer 1

a) We have Context-free grammar because left parts of rules consist of one nonterminal symbol.

b) To prove that aabb$\in$ L(G₁) we give proof string aabb from initial symbol:

S->ASB->aSB->aSb->aASBb->aaSBb->aaSbb->aa$\epsilon$bb=aabb