Programming Examples: Tokenization, Regular Expressions, Derivation Sequences, and More
Programming Examples
Tokenization
Write a program for tokenization of given input:
input_string = input("Enter the input string: ")
tokens = input_string.split()
print(tokens)
Regular Expressions
Write a program for generating regular expressions for regular grammar:
from re import *
list1='Good morning everyone'
x=findall('eve',list1)
print(x)
list2='Good morning everyone & good afternoon'
y=search("everyone",list2)
if y:
print('matched')
else :
print('Not matched')
print('')
list1='Good morning everyone'
x=split('\s',list1)
print(x)
Derivation Sequences
Write a program for generating derivation sequences for the given sequence:
def printArray(arr,size):
for i in range(size):
print(arr[i],end=' ')
print()
return
def getSuccesor(arr,k,n):
p=k-1
while(arr[p]==n and 0<=p<k):
p-=1
if(p<0):
return 0
arr[p]=arr[p]+1
i=p+1
while(i<k):
arr[i]=1
i+=1
return 1
def printSequences(n,k):
arr=[0]*k
for i in range(k):
arr[i]=1
while(1):
#print the current sequence
printArray(arr,k)
if(getSuccesor(arr,k,n)==0):
break
return
n=3
k=2
printSequences(n,k)
Decimal Numbers Divisible by 2
Design a program for accepting decimal numbers divisible by 2:
#String Matching
def stateQ0(n):
if len(n)==0:
print('string accepted')
else:
if(n[0]=='0'):
stateQ0(n[1:])
elif n[0]=='1':
stateQ1(n[1:])
def stateQ1(n):
if len(n)==0:
print('string not accepted')
else:
if(n[0]=='0'):
stateQ0(n[1:])
elif n[0]=='1':
stateQ1(n[1:])
while True:
n=int((input('Enter a string :')))
a=bin(n).replace('0b','')
stateQ0(a)
if n==1313:
break
Strings with Equal 1s and 0s
Design a program for creating a machine which accepts strings having an equal number of 1’s and 0’s:
def getSubStringWithEqual012(s):
arr = []
n = len(s)
for i in range(n):
for j in range(i, n):
s1 = ''
for k in range(i, 1 + j):
s1+=s[k]
arr.append(s1)
count = 0
for i in range(len(arr)):
countZero=0
countOnes=0
countTwo=0
curs = arr[i]
for j in range(len(curs)):
if(curs[j] == '0'):
countZero+=1
if(curs[j] == '1'):
countOnes+=1
if(curs[j] == '2'):
countTwo+=1
if(countZero == countOnes and countOnes == countTwo):
count += 1
return count
Str = "0102010"
print(getSubStringWithEqual012(Str))
Counting 1s and 0s in a String
Design a program for creating machines that count 1’s and 0’s in a given string:
def countSubstring(S, n):
ans = 0
i = 0
# Traversing the string
while (i < n):
cnt0 = 0;cnt1 = 0
if (S[i] == '0'):
while (i < n and S[i] == '0'):
cnt0 += 1
i += 1
else:
j = i
while (j < n and S[j] == '1'):
cnt1 += 1
j += 1
while (i < n and S[i] == '1'):
cnt1 += 1
i += 1
j = i
while (j < n and S[j] == '0'):
cnt0 += 1
j += 1
ans += min(cnt0, cnt1)
return ans
# Driver code
if __name__ == "__main__":
S = "0001110010"
n = len(S)
print(countSubstring(S, n))
Strings Ending with 101
Design a program for creating a machine that accepts strings always ending with 101:
def q1(s, i):
print("q1->", end="")
if (i == len(s)):
print("NO")
return
if (s[i] == '0'):
q1(s, i + 1)
else:
q3(s, i + 1)
def q2(s, i):
print("q2->", end = "")
if (i == len(s)):
print("NO")
return
if (s[i] == '0'):
q4(s, i + 1)
else:
q2(s, i + 1)
def q3(s, i):
print("q3->", end = "")
if (i == len(s)):
print("YES")
return
if (s[i] == '0'):
q4(s, i + 1)
else:
q2(s, i + 1)
def q4(s, i):
print("q4->", end = "")
if (i == len(s)):
print("YES")
return
if (s[i] == '0'):
q1(s, i + 1)
else:
q3(s, i + 1)
def q0(s, i):
print("q0->", end = "")
if (i == len(s)):
print("NO")
return
if (s[i] == '0'):
q1(s, i + 1)
else:
q2(s, i + 1)
if __name__ == "__main__":
s = "010101"
print("State transitions are", end = " ")
q0(s, 0)
PDA for WCWR
Design a PDA to accept WCWR where W is any string, WR is the reverse of that string, and C is a special symbol:
class DPDA:
def __init__(self, trf, input, state):
self.head = 0
self.trf = {}
self.state = str(state)
self.input = input
self.trf = trf
self.stack = ['Z']
def step(self):
a = self.input[self.head]
s = self.stack.pop()
state, ss = self.trf.get((self.state, a, s))
if ss != 'ε':
for s in ss[::-1]:
self.stack.append(s)
self.state = state
print('{:20s} [{:10s}] {:5s}'.format(self.input[self.head:], ''.join(self.stack), self.state))
self.head += 1
def run(self):
print('{:20s} [{:10s}] {:5s}'.format(self.input[self.head:], ''.join(self.stack), self.state))
while self.head < len(self.input):
self.step()
s = self.stack.pop()
if self.trf.get((self.state, 'ε', s)):
state, ss = self.trf.get((self.state, 'ε', s))
self.state = state
print('{:20s} [{:10s}] {:5s}'.format('ε', ''.join(self.stack), self.state))
DPDA({('q', 'a', 'Z'): ('q', 'XZ'), ('q', 'a', 'X'): ('q', 'XX'), ('q', 'b', 'X'): ('p', 'ε'), ('p', 'b', 'X'): ('p', 'ε'), ('p', 'ε', 'Z'): ('acc', 'Z')}, 'aaaaaaaaabbbbbbbbb', 'q').run()