Question

2. Give a finite state machine that defines the language of all “words” using only lower case letters that contain your first name repeated one or more times with exactly two letters (a–z) between each occurrence of your name. For example, words in my language would be: “jim”, “jimaajim”, “jimabjim”, “jimtwjim”, “jimrrjimopjim”, etc.

Answer 1

# lang: seed with base name used in the language
# chars: all possibly character combinations desired between each name
# maxlength: the maximum number of characters per word in the dictionary
def defineLang(lang, chars, maxlength):
count = 0
genlength = len(lang[0])+2
while (len(lang[-1])+genlength) < maxlength:
for word in lang[-count:]:
for c in chars:
lang.append(word+c+lang[0])
count += genlength
return lang

def createMix(n):
charmix = []
#create the mix of all possible 2 letter combinations
for a in range(n):
a_ch = chr(97+a)
for b in range(n):
charmix.append(a_ch+chr(97+b))
return charmix

print defineLang(["Corbin"],createMix(26),15)

This is very close to working, but it has a problem with some duplicate results. As far as I can tell I think the only duplicates are with the first {name}{chars}{name}. I'm probably overlooking a stupid mistake. I'll come back and work on it more later if no one else has any suggestions.

Answer 2

oh by the way, that is in python

Answer 3

Isn't a finite state machine one that either accepts or rejects an input based on the grammar? I would write a recursive function:
if input == <name>: return true
if the start of the input is <name><letter><letter><name><rest of input>:
recurse with <name><rest of input>
else return false

Answer 4

What do you need to write when you are asked for finite state machine? Do you mean something like DFA or NFA? or program?

Answer 5

That's a very good question. And it depends on Tektronix' assignment.
But all automata are pretty much the same, in theory. Whether it's a state diagram, a BNF description of the language, a computer program or script to simulate it, or if you still have a paper tape reader/writer and soldering iron....