Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Non-regular Language

No description
by

on 7 May 2015

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Non-regular Language

Non-regular Language
Presented by:
Muneeb-ur-Rahman(544)
Bilal Imrani(523)

Non-regular Language
A language that cannot be defined by a regular expression is called nonregular language.
By Kleene's theorem a nonregular language can also not be accepted by any FA or TG.
All languages are either regular or noregular language;none are both

But any finite automaton has only finite number of states. Thus there is no way for a finite automaton to remember how many a's it has read for all possible strings anbn . That is the main limitation of finite automata. Since a regular language must be recognized by a finite automaton, we can conclude that { anbn | n is a natural number} is not regular. This is the basis of two of the regularity test methods we are going to study below: Myhill-Nerode Theorem and Pumping Lemma.
The main idea behind these test methods is that finite automata have only finite amount of memory in the form of states and that they can not distinguish infinitely many strings. For example to recognize the language { anbn | n is a natural number} , a finite automaton must remember how many a's it has read when it starts reading b's. Thus it must be in different states when it has read different number of a's and starts reading the first b.
Pumping Lemma is a tool that enable us to prove that certain other languages are also nonregular.
This is contradiction.we wre assume that we were talking about an FA that accepts exactly thw words in L and then we were able to prove that the same machine accepts some words that is not in L.Means that the machine that accepts the words in L does not exist.in other word L is nonregular.
Theorem 13
let L be any regular language that has infinitely many words.then there exist some three strings x,y,z.
where y is not null string
xynz
Proof:

there are three parts.
part 1:Call part X all the letters of W starting at the begining that lead up to the first state that is revisited.notice that X me the null stringif the path for w revisits the start state as its first revisits

Part 2:
starting at the leeter fter the substring x,let y denote the substring of w that travels around the circuit coming back to the same state the circuit began with.because there must be a circuit.y contains the letter of w for exactly one loop around this circuit

Part 3:
let Z be the rest of w starting with the letter after the substring y and going to the end of the string w.this z could be null.

w=xyz
Full transcript