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.1k points) | 63 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

36,132 questions
43,577 answers
42,815 users