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

asked in Theory of Computation by (181 points) | 31 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 Active (2.4k 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 (11 points)

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

36,157 questions
43,608 answers
42,860 users