Welcome! Log In Create A New Profile

Advanced

non-regular

Posted by kiolb 
Announcements Last Post
Announcement SoC Curricula 09/30/2017 01:08PM
Announcement Demarcation or scoping of examinations and assessment 02/13/2017 07:59AM
Announcement School of Computing Short Learning Programmes 11/24/2014 08:37AM
Announcement Unisa contact information 07/28/2011 01:28PM
avatar non-regular
July 04, 2008 10:21AM
It seems that non-regular languages are a sub set of regular languages. (example on page 193), but the diagram on page 574 shows regular languages as a sub set of all other languages. Also page 3 of guide says regular languages are at the lowest level.

So are all the other languages non-regular?
and then regular languages a sub set of these?

Thanks
B
Re: non-regular
July 10, 2008 11:11AM
Why do you say 'non-regular languages are a sub set of regular languages. (example on page 193)'?


As stated on p 187 any language can only be either regular or nonregular.

The diagram on p. 574 illustrates classes of languages. A regular language can be generated by a regular expression, and it will also be accepted by a PDA (context free) and also by a Tring Machine (recursive) as described in COS301.
avatar Re: non-regular
July 18, 2008 09:40AM
i) The last sentence on page 573 of Cohen refers to the Venn diagram on page 574. Also wikipedia refers to the Chomsky Hierarchy with the lower (inner) levels as proper subsets of the higher. See http://en.wikipedia.org/wiki/Regular_language

ii) Why I say 'non-regular languages are a sub set of regular languages. (example on page 193)'?
On the top of page 188 in Cohen, that is what he says.smile (anbn is a subset of a*b* for n >= 0).
With the example on pg 193. The intersection of a*b* and EQUAL is anbn, which is non-regular, because EQUAL is non-regular. So anbn is a subset of regular and non-regular.

iii) Also in Cohen, question 15 of chapter 10 asks for examples of languages:
a*b* = a*b* + anbn (regular = regular + non-regular) (+=union [and])
and
let R = {bbaa, ba} and N = bnan, then N=R+N (non-regular = regular + non-regular) (+=union [and])

iv)
Quote
becked
The diagram on p. 574 illustrates classes of languages. A regular language can be generated by a regular expression, and it will also be accepted by a PDA (context free) and also by a Turing Machine (recursive) as described in COS301.

So regular languages are in other classes of languages?
If the regular class consists of regular languages, then are the other classes non-regular?

- So, to me, non-regular languages are a subset of regular languages. From (ii) and (iii) above.
- If regular languages are in other classes (from (iv)), then regular languages will be a subset of non-regular languages. From (i), (iii) above.
- A language is either regular or non-regular.

Ummmm. Well!!! Yes!!!!!!!!!!!

I can actually understand this to be true. Surprisingly. Or am I totally mad.
Re: non-regular
July 25, 2008 03:11PM
Remember, a language is a set and must be indicated by { }. Eg a*b* is the expression and {a*b*} is the language.

The top of p.188 refers to one example, so one cannot make a general statement saying 'non-regular languages are a sub set of regular languages'. This is NOT true.

The Venn diagram on page 574 should be interpreted as follows: All regular languages are also context free-languages, all contect-free languages are also recursive languages, all recursive languages are also recursively enumerable languages, etc. The "non-regular languages" on that Venn diagram are the languages AROUND the innermost set, i.e. a nonregular language cannot be a regular language. The diagram is not supposed to be used for this. There is NO category called nonregular. Remember that this Venn diagram indicates that certain categories are subsets of other categories - not languages subsets of other languages.

In COS301 you will learn that a context-free language is accepted by a PDA and a recursive language is accepted by a TM. In Wikipedia it is stated that "Each category of languages or grammars is a proper subset of the category directly above it and any automaton in each category has an equivalent automaton in the category above it". This means: There will be a PDA that accepts any given regular language. There will be a TM that accepts any given contextfree langauge, etc.
Re: non-regular
October 22, 2008 02:20PM
if we don't understand a word you 2 are saying, are we in trouble for the exam ?
Re: non-regular
October 23, 2008 08:23AM
No, this is not relevant study material.
Sorry, only registered users may post in this forum.

Click here to login