Peter Linz Edition 4 Exercise 2.1 Question 12 (Page No. 48)

Question

Show that $L=$ {$a^n: n ≥4$} is regular.

Comments

We can draw the DFA for this or a regular expression and either a LR(left recursive) or RR(right recursive) grammar.For a grammar to be regular , there has to be a loop present in the grammar.

Also, if a grammar is both left recursive and right recursive,it cannot be regular. (because it produces ambiguity)

 

DFA:

a^n: n ≥4
 

 

 

 

 

 

Regular Expression: aaaa(a$^{*}$)

 

Grammar: 

A->aaaaB

B->aB | $^{\epsilon  }$     <= THIS IS RIGHT RECURSIVE GRAMMAR

 

We can also write a left recursive grammar for this 

A->Baaaa

B->Ba | $^{\epsilon  }$     <= THIS IS LEFT RECURSIVE GRAMMAR.

Answer 1

we can draw a dfa for this . so it is regular