Search code examples
formal-languages

What would be the language generated by Σ*-x?


Say, for example, Σ={x,y}. And you carried out the operation Σ*-x. What would be the resulting language? Would it essentially be y* or would it just minus one occurrence of x in all strings generated in Σ*? i.e xxyyxx to xyyxx.


Solution

  • It would be the language of all strings generated by Σ* minus the string x. (so: xx, epsilon, xyx, y, etc... but not x)