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

Let Σ = {a, b}. Given words u, v ∈ Σ*  , we say that v extends u if v is of the form xuy for some x, y ∈ Σ*  . Given a fixed word u, we are interested in identifying whether a finite state automaton accepts some word that extends u.

Describe an algorithm that takes as input a finite state automaton (DFA or NFA) A over Σ = {a, b} and a word u ∈ Σ*  and reports “Yes” if some word in the language of A extends u and “No” if no word in the language of A extends u.

asked in Theory of Computation by Boss (16.6k points) | 64 views

Please log in or register to answer this question.

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

39,778 questions
46,781 answers
58,672 users