The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
0 votes

asked in Theory of Computation by Junior (779 points) | 51 views

2 Answers

0 votes

your initial state =n0

let assume it as 0... while reading 'a' going to one state forward...that implies adding 1 to previous state

while reading 'b' going to one state backward... that implies decreasing 1 to  previous state...

if you have same no.of a's and b's ===> finally you are at initial position only

but you are aim is go to n5 only.....therefore you should have exactly 5 more a's than b's to reach final state... Option : B is correct

answered by Veteran (60.7k points)
0 votes
Answer: B

Starting with state {0},encountering 'a' would add 1 to present state and encountering 'b' would subtract 1 from present state.Since the final state is {5} hence the accepted strings will be a^5,a^6 b,a^7 b^2,... considering an 'a' as +1 and 'b' as -1.Hence the number of a's is 5 more than b.
answered by (411 points)

Related questions

0 votes
0 answers
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,407 questions
53,589 answers
70,870 users