#practicle 1
# Write a program for generating regular expressions for regular grammar in Python.
import re
line = "horses are taller than dogs"
searchObj = [Link](r"(.*) are (.*?) .*", line, re.M | re.I)
if searchObj:
print("[Link]() : ", [Link]())
print("[Link](1) : ", [Link](1))
print("[Link](2) : ", [Link](2))
else:
print("Nothing found!!")
===================================================================================
===================================================================================
=======
#practicle 2
# Write a program for generating derivation sequence / language for the given
sequence of productions in Python.
def printArray(arr, size):
for i in range(size):
print(arr[i], end=" ")
print()
def getSuccessor(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):
printArray(arr, k)
if(getSuccessor(arr, k, n) == 0):
break
# Driver code
n = 3
k = 2
printSequences(n, k)
===================================================================================
===================================================================================
=======
#practicle 3
# Design a Program for creating machine that accepts the string always ending with
101 in python.
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)
# Driver Code
if __name__ == "__main__":
s = "010101"
print("State transitions are", end=" ")
q0(s, 0)
===================================================================================
===================================================================================
=======
#practicle 4
# Design a program for creating machine that accepts three Consecutive one in
Python.
def stateA(n):
if n[0] == 'a':
stateB(n[1:])
elif n[0] == 'b':
stateH(n[1:])
def stateB(n):
if len(n) == 0:
print("String Not Accepted")
else:
if n[0] == 'a':
stateC(n[1:])
elif n[0] == 'b':
stateI(n[1:])
def stateC(n):
if len(n) == 0:
print("String Not Accepted")
else:
if n[0] == 'a':
stateD(n[1:])
elif n[0] == 'b':
stateJ(n[1:])
def stateD(n):
if len(n) == 0:
print("String Not Accepted")
else:
if n[0] == 'a':
stateQ2(n)
elif n[0] == 'b':
stateE(n[1:])
def stateE(n):
if len(n) == 0:
print("String Not Accepted")
else:
if n[0] == 'a':
stateQ2(n)
elif n[0] == 'b':
stateF(n[1:])
def stateF(n):
if len(n) == 0:
print("String Not Accepted")
else:
if n[0] == 'a':
stateQ2(n[1:])
elif n[0] == 'b':
stateG(n[1:])
def stateG(n):
if len(n) == 0:
print("String Accepted")
else:
if n[0] == 'a':
stateQ2(n)
elif n[0] == 'b':
stateQ2(n)
def stateH(n):
if len(n) == 0:
print("String Not Accepted")
else:
if n[0] == 'a':
stateI(n[1:])
elif n[0] == 'b':
stateK(n[1:])
def stateI(n):
if len(n) == 0:
print("String Not Accepted")
else:
if n[0] == 'a':
stateJ(n[1:])
elif n[0] == 'b':
stateL(n[1:])
def stateJ(n):
if len(n) == 0:
print("String Not Accepted")
else:
if n[0] == 'a':
stateE(n[1:])
elif n[0] == 'b':
stateM(n[1:])
def stateK(n):
if len(n) == 0:
print("String Not Accepted")
else:
if n[0] == 'a':
stateL(n[1:])
elif n[0] == 'b':
stateN(n[1:])
def stateL(n):
if len(n) == 0:
print("String Not Accepted")
else:
if n[0] == 'a':
stateM(n[1:])
elif n[0] == 'b':
stateO(n[1:])
def stateM(n):
if len(n) == 0:
print("String Not Accepted")
else:
if n[0] == 'a':
stateF(n[1:])
elif n[0] == 'b':
stateP(n[1:])
def stateN(n):
if len(n) == 0:
print("String Not Accepted")
else:
if n[0] == 'a':
stateO(n[1:])
elif n[0] == 'b':
stateQ1(n)
def stateO(n):
if len(n) == 0:
print("String Not Accepted")
else:
if n[0] == 'a':
stateP(n[1:])
elif n[0] == 'b':
stateQ1(n)
def stateP(n):
if len(n) == 0:
print("String Not Accepted")
else:
if n[0] == 'a':
stateG(n[1:])
elif n[0] == 'b':
stateQ1(n[1:])
def stateQ1(n):
print("String Not Accepted")
def stateQ2(n):
print("String Not Accepted")
# take string input
n = "abaabb"
# call stateA
# to check the input
stateA(n)
===================================================================================
===================================================================================
=======
# Practical 5
#To accept decimal number divisible by 2 in python
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:])
n = int(input())
binary_representation = bin(n)[2:] # Convert to binary and remove '0b' prefix
stateq0(binary_representation)
===================================================================================
===================================================================================
=======
# practical 6
# Design a program for creating a machine which accepts string having equal no of
1’s and 0’s in Python.
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]
[Link](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 = input() # take input from user at runtime
#input 10021020 or use Str = "10021020"
print(getSubStringWithEqual012(Str))
===================================================================================
===================================================================================
=======
# practical 7
# Design a program for creating a machine which count number of 1’s and 0’s in a
given string in python.
def countSubstring(S, n):
ans = 0
i = 0
while i < n:
cnt0 = 0
cnt1 = 0
if S[i] == '0':
while i < n and S[i] == '0':
cnt0 += 1
i += 1
j = i
while j < n and S[j] == '1':
cnt1 += 1
j += 1
else:
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
if __name__ == "__main__":
S = "0001110010"
n = len(S)
print(countSubstring(S, n))
===================================================================================
===================================================================================
=======
# practical 8
# Design a PDA to accept WCWR where w is any string and WR is reverse of that
string and C is a Special symbol.
#or
# Deterministic Pushdown Automata for L = a^nb^n | n >=0) Python Program
class DPDA:
def __init__(self, trf, input, state):
[Link] = 0
[Link] = {}
[Link] = str(state)
[Link] = input
[Link] = trf
[Link] = ['Z']
def step(self):
a = [Link][[Link]]
s = [Link]()
state, ss = [Link](([Link], a, s))
if ss != '$':
for s in ss[::-1]:
[Link](s)
[Link] = state
print('{:20s} [{:10s}]
{:5s}'.format([Link][[Link]:],''.join([Link]), [Link]))
[Link] += 1
def run(self):
print('{:20s} [{:10s}]
{:5s}'.format([Link][[Link]:],''.join([Link]), [Link]))
while [Link] < len([Link]):
[Link]()
s = [Link]()
if [Link](([Link], '$', s)):
state, ss = [Link](([Link], '$', s))
[Link] = state
print('{:20s} [{:10s}] {:5s}'.format('$',''.join([Link]),
[Link]))
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()