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.3k
- Engineering Mathematics 5.2k
- Digital Logic 2k
- Programming & DS 3.7k
- Algorithms 3.2k
- Theory of Computation 4k
- Compiler Design 1.6k
- Databases 3k
- CO & Architecture 2.6k
- Computer Networks 3k
- Non GATE 1k
- Others 1.3k
- Admissions 486
- Exam Queries 434
- Tier 1 Placement Questions 17
- Job Queries 56
- Projects 9

36,132 questions

43,577 answers

123,845 comments

42,815 users