SGT Sheet

Question 1

Alphabet $\Sigma =\{0,1\}$, construct a DFA or NFA that accepts:

1. Binary strings that being and end with $1$.

digraph {
	label="(1) DFA"
	rankdir=LR
	init[shape=point]
	node[shape=doublecircle]; r;
	node[shape=circle];
	init->s
	
	s->p [label=0]
	s->q [label=1]
	q->r [label=1]
	q->q [label=0]
	r->q [label=0]
	r->r [label=1]
 
	# always fail
	p->p [label=0]
	p->p [label=1]
}

Fail

Does not check single length.

digraph {
	label="(1) NFA"
	rankdir=LR
	init[shape=point]
	node[shape=doublecircle]; q;
	node[shape=circle];
	init->s
	
	s->q [label=1]
	q->r [label=0]
	r->q [label=1]
}

2. Strings that contain exactly three $1$s.

digraph {
	label="(2) NFA"
	rankdir=LR
	init[shape=point]
	node[shape=doublecircle]; r;
	node[shape=circle];
	init->s
	
	s->p [label=1]
	s->s [label=0]
	p->q [label=1]
	p->p [label=0]
	q->r [label=1]
	q->q [label=0]
	
	r->r [label=0]
	r->t [label=1]
}

Correct

3. Contain substring $1010$.

digraph {
	label="(3) NFA"
	rankdir=LR
	init[shape=point]
	node[shape=doublecircle]; u;
	node[shape=circle];
	init->s
 
	s->s [label=0]
	s->s [label=1]
	s->q [label=1]
	q->r [label=0]
	r->t [label=1]
	t->u [label=0]
	
	u->u [label=0]
	u->u [label=1]
}

Correct

4. Regular language represented by expression $1(01{)}^{\ast }1$.

digraph {
	label="(4) NFA"
	rankdir=LR
	init[shape=point]
	node[shape=doublecircle]; t;
	node[shape=circle];
	init->s
	
	s->p [label=1]
	
	p->q [label=0]
	q->r [label=1]
 
	r->q [label=0]
	r->t [label=1]
 
	p->t [label=1]
}

Correct

Alternative Solution

digraph {
	label="NFA"
	rankdir=LR
	init[shape=point]
	node[shape=doublecircle]; u;
	node[shape=circle];
	init->s
	
	s->q [label=1]
	q->r [label=0]
	r->t [label=1]
	t->u [label=1]
 
	q->t [label=ε]
	t->q [label=ε]
}

Question 2

Let $\Sigma =\{0,1,\#\}$.

1. Which are accepted:
   1. $1001$: Yes
   2. $00$: No
   3. $101$: No
   4. $0011$: Yes

Correct

2. All strings with the same number of $1$s as $0$s.

Correct

Question 3

$\Sigma =\{0,1\}$ $L=\{w\in \{0,1{\}}^{\ast }:w=w^R\}$ $w^R$ denotes reversal of $w\in \{0,1{\}}^{\ast }$

1. $1$, $0$, $101$, $010$, $11011$

Correct

3. Assumption: we only have one tape to work with High-level description:

   • Read first digit and remember whether 0 or 1.
   • Seek to end of string
   • Check whether last digit matches
   • Remove last digit
   • Seek to start and remove first digit
   • Seek to next digit until no digits are left Pseudo-code:

   qInit: if read _: state qAccept else read 0: state q0Seek else read 1: state q1Seek

   q0Seek: if read _: move left state q0Check else: move right state q0Seek

   q1Seek: if read _: move left state q1Check else: move right state q1Check

   q0Check: # read _ is invalid if read 1: state qReject else read 0: write _ move left state qSeekStart

   q1Check: # read _ is invalid if read 0: state qReject else read 1: write _ move left state qSeekStart

   qSeekStart: if read _: move right state qDelete else: move left

   qDelete: if read _: # palindrome of 1 char state qAccept else: write _ move right

    	state qInit
   

Correct

3. Convert pseudo-code into a complete description of a Turing Machine

digraph {
	label="TM (implicit reject)"
	rankdir=LR
	init[shape=point]
	node[shape=doublecircle]; qAccept;
	node[shape=circle];
	init->qInit
 
	# read first digit
	qInit->qAccept [label="_,_,-"]
	qInit->qSeek0 [label="0,0,>"]
	qInit->qSeek1 [label="1,1,>"]
	
	# seek to the end of the string
	qSeek0->qCheck0 [label="_,_,<"]
	qSeek0->qSeek0 [label="0,0,>"]
	qSeek0->qSeek0 [label="1,1,>"]
	qSeek1->qCheck1 [label="_,_,<"]
	qSeek1->qSeek1 [label="0,0,>"]
	qSeek1->qSeek1 [label="1,1,>"]
 
	# check if end of string matches
	qCheck0->qSeekStart [label="0,_,<"]
	qCheck1->qSeekStart [label="1,_,<"]
 
	# seek to start
	qSeekStart->qDelete [label="_,_,>"]
	qSeekStart->qSeekStart [label="0,0,<"]
	qSeekStart->qSeekStart [label="1,1,<"]
 
	# delete and restart process
	qDelete->qAccept [label="_,_,-"]
	qDelete->qInit [label="0,_,>"]
	qDelete->qInit [label="1,_,>"]
}

name: Binary Palindrome
init: qInit
accept: qAccept

// read first digit
qInit,_
qAccept,_,-

qInit,0
qSeek0,0,>

qInit,1
qSeek1,1,>

// seek to end of string
qSeek0,_
qCheck0,_,<

qSeek0,0
qSeek0,0,>

qSeek0,1
qSeek0,1,>

qSeek1,_
qCheck1,_,<

qSeek1,0
qSeek1,0,>

qSeek1,1
qSeek1,1,>

// check if end of string matches
qCheck0,0
qSeekStart,_,<

qCheck1,1
qSeekStart,_,<

// seek to start
qSeekStart,_
qDelete,_,>

qSeekStart,0
qSeekStart,0,<

qSeekStart,1
qSeekStart,1,<

// delete and restart process
qDelete,_
qAccept,_,-

qDelete,0
qInit,_,>

qDelete,1
qInit,_,>

Correct

Question 4

Show that no DFA can accept the language $L=\{w\#w:w\in \{0,1{\}}^{\ast }\}$.

• Assume a DFA $A$ accepts $L$.
• Let $p$ be equal to the number of states.
• Let $w_1$ be $a^k\#1^k$, by definition $w_1\in L$ for some $k>p$.
• By the pigeon-hole principle, there exists state $q$ which is visited at least twice.
• Assume the first visit is at time $t_1$ and second at time $t_2$.
• Hence we have that, $1^{k-(t_2-t_1)}\equiv 1^k$.
• We have that $A$ accepts $w_2=2^{k-t}\#1^k$, but $w_2\notin L$.
• This is a contradiction.

This is the correct answer