#TOC DOUBT

Question

A)Is it useful to draw FA  if we need to tell the language of the following grammar...?

B)What is the language of the following grammar..?

C) What will be the final state Of FA and what is the criteria to find out final state.if a given a regular grammar.?

 

S→aB|bA
A→aS|bAA|a
B→bS|aBB|b

Comments

A)  Yes , it is easier if u find  by constructing a finite automata for it . On practising many questions you will be able to judge the language accepted by the grammar without the automata , in that case you can do it directly because it will save time for you :)

C) A and B are final states because you can see that they have terminals , so obviously the string can end there with a terminal and get accepted

---

(B)L={ab,ba,abab,baba........}

---

@abhishek tiwary Can you please more elaborate....i mean it is accepting :-

a) equal no of a's and b's

b) a's are greater than b's

c) b's are greater than a's

d)None of these'

---

@AISH thanks for useful knowledge, but it will be more clear if you give examples like in this case if A and B is a final state then can you help me drawing dfa for it...and it is a RLG

---

The given grammar is context free, you cannot draw a DFA for it. It accepts $\left \{ w| w \epsilon \left ( a+b \right )^{+} , n_{a}\left ( w \right ) = n_{b}\left ( w \right ) \right \}$

---

@just_bhavana how you able to make it

by deriving the strings and guessing the language for same..

---

just try to enumerate the strings in the grammar, you'll get an idea

---

No, I don't think A and B are the final states. Here, S is the final state.

---

First of all this grammar is not regular ,then how can you make dfa by this grammar?? For designing dfa or nfa ,right linear grammar is best .but above grammar is not even linear grammar.

---

Oh Yes, you are right Prateek. Thanks!

Answer 1

A)if a grammar is left linear or right linear grammar then we can drow a dfa .
But here grammar is not left or right linear grammar . So we cant drow DFA.

B)L={ab,ba,abab,aabb,baba......}
Language gives equal no of a's and equal no of b's .

C) it is a CFL but not regular . Then we can not drow FINITE AUTOMETA. we can drow PDA for this.