The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

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.*

- All categories
- General Aptitude 1.4k
- Engineering Mathematics 5.7k
- Digital Logic 2.2k
- Programming & DS 4.1k
- Algorithms 3.6k
- Theory of Computation 4.5k
- Compiler Design 1.7k
- Databases 3.2k
- CO & Architecture 2.8k
- Computer Networks 3.2k
- Non GATE 1.1k
- Others 1.5k
- Admissions 503
- Exam Queries 474
- Tier 1 Placement Questions 22
- Job Queries 61
- Projects 13

39,778 questions

46,781 answers

140,752 comments

58,672 users