Is the following language regular? context free?

Question

Given the following language:

L = { bi | i > 0 } U {aibi | i > 0 }

Is this language context free? regular?

I tried thinking about it, but no results so far..

Answer 1

L = { bi | i > 0 } U {aibi | i > 0 } is Context-Free or a Regular language?

Language L is 'Context Free Language', In language L {aibi | i > 0 } is subset of strings that makes L a context free language that means if string starts with a then string should have equal number of b (in prefix), and for counting how many as has been come we need a PDS memory (this can't be processes using FA because of finite memory available in FA).

Grammar for L will be:

S --> A | B   
B --> b | Bb  
A --> ab | aAb

Hint for grammar: Either string can start with b and can contains any number of b (if string starts with b then no a allowed). If string starts with a then string patter should be {aibi | i > 0 }.

I suggest you to read: "What is a regular language?" What is basically a regular language? And Why a*b* is regular? But language { anbn | n > 0 } is not a regular language

Answer 2

Why isn't the specified language not regular?

This can be proved either by using the pumping lemma or by realizing the fact that the language contains infinite number of pairwise distinguishable strings. FSA having limited memory cannot accept the same.

Language can be proved to be a CFL by writing a CFG (as pointed by @Grijesh) which generates the same or by designing a Push Down Automata.

In addition to being a context free language the specified language : L = { bⁱ | i > 0 } U {aⁱbⁱ | i > 0 }

is also a deterministic context free language. Deterministic CFL's are a subset of Context Free Languages which are closed under compliment and intersection unlike the class of CFL's . The Deterministic CFL's are also closed under intersection with Regular Languages which helps us prove that the given language is a DFCL.

L∪R = (L ^c ∩ R ^c) ^c