CODEWITHSUNDEEP
automata
pioardi
pioardi

Reputation: 181

Are those languages regular or not

Hi I would need help from you, I got the following languages and need to determine if are regular or not.

enter image description here

Now I think that Y is not regular and I applied the Pumping Lemma to determine that. For X I am not sure if is a regular language or not, I was thinking that X is the set of strings with an odd number of a's that can be easily represented with an NFA.

Can anyone help me with that ?

Upvotes: 1

Views: 39

Answers (1)

Nikolay Handzhiyski
Nikolay Handzhiyski

Reputation: 1579

The first one (X) is regular, because you can construct a finite automaton for it:

(start) --- a --> (final) -- a --> (state)
                     ^                |
                     \------ a -------/

The second one (Y) is not regular, because you cannot construct a finite automaton for it. It would require memory to store the number of a to be able to later find one more of b. That language is context-free, with a grammar:

S = T b
T = a T b
T = ε

Upvotes: 1

Related Questions