Finit Automata

Question

The possible number of prefixes for the given 'n' length string is (assume all symbols in the given string are different)

a) n

b) n+1

c) n+2

d) n-1

please explain.

Comments

suppose $abcd$ is a string,

then prefixes will be $\epsilon,a,ab,abc,abcd$.

I think it should be $n+1$

in case of proper prefix, all will be there except $\epsilon$ and $abcd$, i.e, $a,ab,abc$ means $n-1$

---

Praveen saini sir in case of proper prefix all will be there except epsilon and abcd ..did you exclude string d also..if yes Y?

---

d is not a prefix.

---

Proper prefixes means (prefixes -string)..

In proper prefixes even epsilon included .

Answer 1

Ans  N + 1

String= abc

Prefix = {epislon, a, ab, abc}

Answer 2

N+1.

let string be abcd.

prefixes are = { epsilon, a, ab, abc, abcd}

Answer 3

Let's take a string=gate.Now the prefixes possible are:
{g,ga,gat,gate,epsilon}=5=N+1
Similarly suffixes are:{epsilon,gate,ate,te,e}=5=N+1.

Comments

Epsilon also comes in suffix ?why

Answer 4

Consider the string 011 over the binary alphabet. All the prefixes, suffixes, and substrings of this string are listed below.

Prefixes: $\varepsilon$, 0, 01, 011.
Suffixes: $\varepsilon$, 1, 11, 011.
Substrings: $\varepsilon$, 0, 1, 01, 11, 011.

Note that x is a prefix (suffix or substring) to x, for any string x and $\varepsilon$ is a prefix (suffix or substring) to any string.

A string x is a proper prefix (suffix) of string y if x is a prefix (suffix) of y and $x\neq y$

In the above example, all prefixes except 011 are proper prefixes.

Answer 5

N+1 as it will contain {ɛ,a,ab,abc}

Comments

@Purvi Agrawal @AnilGoudar Mate, what if the string has non distinct letters say "aaa"

---

iarnav I think it should be N+1

suppose aaa is a string,

then prefixes will be ϵ,a,aa,aaa.

Answer 6

Answer is  b option

Suppose ab is string

Then prefix is {€, a, ab}

Hence answer is n+1