How to find the language of a NFA

Question

As above, I have a transition graph, but I'm not sure how to find the language of it, seems to me that there are a lot of possibilities, but I must be misunderstanding somehow. My understanding is that any word that leads from the initial to the final state is accepted. Surely there are a lot of different ways to achieve this. aab, ab, abb, abbaab. As I understand it, a language is a set of all the possible words, but if there are a vast amount of possible words, how can you find the language? Im a first year University student, this is part of my homework, but I'm not just trying to get you to do it for me, I want to understand it - if this doesn't make sense/ is in the wrong place I apologise in advance, thanks. Here's my graph

Answer 1

Some regular languages are finite - they contain a finite number of strings. When you have a finite number of things, that means you can count them all and get to the end eventually; you can write them all down if they're words in a language. Writing down all the words in a language is a way of giving an extensive definition of a language.

However - there are languages which are not finite. They do not contain any number of words you can count from beginning to end, or ever completely write down. If you think of all natural numbers (1, 2, …, 100, …) as strings in the language of decimal representations, clearly there are not finitely many of them. There are infinitely many. You cannot give extensive definitions of infinite languages (except, possibly, by suggestive use of the ellipsis, as I have done in my example). In these cases, you must describe the strings which are included and/or excluded and rely on the reader to deduce membership for any particular case.

Giving a finite automaton is one perfectly reasonable way of giving a criterion according to which membership in the language can be determined: run the string through the automaton and see if it is accepted. In this sense, asking what the language of a finite automaton is can be viewed as trivial: it accepts the language of strings that leave the finite automaton in an accepting state.

Another way of describing the language is to give a grammar or, for regular languages, a regular expression. These are not necessarily more or less helpful ways of describing a language than the finite automaton you already have is.

Typically, in coursework, when you are asked to describe the language of a finite automaton, you are probably being asked to give a plain, English-language definition - a simple one - of the strings, and possibly provide some set-builder notation. That's what we'll try to do here.

Your NFA loops in q0, accepting any number of a, until it sees at least one a. If it sees a b before an a, it crashes. After that, if it sees at least one b, it can accept; it can see any number of b, but after the initial run of a, it can never again see two a in a row. The machine accepts only if it ends with a b.

Taken together, this might be a description in plain English that is good for this language:

All strings that begin with at least one a, which end with b and which do not contain the substring aa after the first instance of b.

A regular expression for this language is aa*(bb*a)*.