October 20th, 2014, 05:03 AM  #1 
Newbie Joined: Oct 2014 From: Sweden Posts: 1 Thanks: 0  Discrete Mathematics
Hi!! I'm in deep trouble. I cannot figure out how to solve a problem in discrete mathematics. And it is the last problem I need to solve. Been working on this one for a long time and feel like I would definitely need some help if you have the time... A nondeterministic finite automaton is a finite automaton in which the same input from the same state may lead to several different possible transitions. A nondeterministic finite automaton accepts an input string if at least one of possible sequence of transitions leads to an accepting state. Prove that for any regular language it is possible to construct a nondeterministic finite automaton with a single accepting state that recognizes the language. Hint! Start by showing how to construct an automaton that recognizes a single symbol or λ. Then show how to construct three nondeterministic automata, each with a single accepting state, to recognize the composite languages R1 + R2, R1R2 and R1*, given that you already have such automata for the regular languages R1 och R2. Explain how an induction argument completes the proof. Can you help me with this one? Last edited by skipjack; November 19th, 2014 at 01:38 AM. Reason: Added missing "fi" and "ff" 
October 20th, 2014, 06:55 AM  #2 
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms 
Some letters were lost when you copy/pasted this  "nite automaton" is "finite automaton" and "dierent" is "different". It may be easier to read the original http://www.mdh.se/polopoly_fs/1.6275...201415ht.pdf see p. 18 for this problem. The hint seems to be very explicit  I would follow it. Which are the steps are you having trouble with? 1. Construct an automaton to accept a single letter, say "x". 2. Construct an automaton to accept λ (is this your notation for the empty string?) 3. Given automata to match languages R1 and R2, construct an automaton to match R1 + R2 (either R1 or R2). 4. Given automata to match languages R1 and R2, construct an automaton to match R1R2 (R1 followed by R2). 5. Given an automaton to match language R1, construct an automaton to match R1* (zero or more instances of R1). 6. Using 15, construct an automaton to accept any regular language (by induction). 
November 18th, 2014, 05:39 AM  #3 
Senior Member Joined: Apr 2014 From: Glasgow Posts: 2,133 Thanks: 719 Math Focus: Physics, mathematical modelling, numerical and computational solutions 
If you copy and paste from a pdf, 'ff' and 'fi' doesn't get interpreted correctly and it doesn't go into your clipboard. You have to type it out manually or link the original pdf.

November 23rd, 2014, 03:38 AM  #4 
Newbie Joined: Nov 2014 From: Kazakhstan Posts: 1 Thanks: 0  Find all automorphisms of the following graph:
Find all automorphisms of the following graph. Also, Prove that there are no more automorphisms than those you listed in part 1.


Tags 
discrete, mathematics 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Discrete Mathematics.  Shruthi318  Applied Math  0  November 9th, 2013 10:42 PM 
Discrete mathematics question  mathboss  Applied Math  0  January 18th, 2013 05:33 AM 
discrete mathematics  conradtsmith  Abstract Algebra  1  April 19th, 2010 08:02 AM 
discrete mathematics  conradtsmith  Number Theory  1  April 19th, 2010 07:11 AM 
Discrete Mathematics.  Shruthi318  Complex Analysis  0  December 31st, 1969 04:00 PM 