formal-languages

  1. Show that the Pumping Lemma for CFLs is not powerful enough to prove that the language L = {aibjck |i ≠j ≠ k ≠ i } is not context free
  2. Proving that $(A \cup B)^* = A^*(BA^*)^*$

  3. If L is regular, is Pref[ Suff (L)] = L?
  4. Prove that the language $L_1 = \{a^ib^{2i}c^j \;|\; i,j ≥ 0\}$ is context-free

  5. Prove grammars with long derivations generate infinite languages

  6. How to show that a "reversed" regular language is regular

  7. A second question on "Show a TM-recognizable language of TMs can be expressed by TM-description language of equivalent TMs"

  8. Constructive Proof on Regular Languages

  9. Is there a standard way to define a formal language transformer?

  10. Proving P and NP on problems formulated as languages

  11. Kleene positive closure - help in proofing this claim

  12. Formalism for unambiguous context-sensitive languages?

  13. Is there a way to find a simple regular expression for this language?
  14. context free grammar for "odd number of 1 and one 0" or "even number of 1"

  15. Show that the collection of Turing-recognizable languages is closed under homomorphism

  16. Closure of Turing-recognizable languages under homomorphism
  17. Thompson Regular Expression Search Algorithm 3rd Stage

  18. How to define a language for an independent set problem of a graph?
  19. Can the regular image of a context-free language be undecidable?

  20. Looking for a subclass of deterministic context-free languages, other than the subclass of regular languages
  21. Concatenation of two regular languages

  22. Turing machine that accepts L = {#a != #b}

  23. Constructing an FSA, where Ratio of number of states of FSA to its Minimal DFA Equivalent < 0.5
  24. Conversion of ambiguous left recursive grammar to LL(1)
  25. Is there an NFA whose corresponding DFA has lesser number of states than the given NFA? (without unreachable states or epsilon moves)
  26. A doubt regarding the acceptance of $\epsilon$ by an automaton testing divisibility of numbers

  27. Can someone give a generic definition of any Definite Language in set builder notation?

  28. Closure of context-free languages under "removal of a regular language from the right"

  29. What are definite languages? How do you formally define them?

  30. CFG - Left factoring in recursive nested productions
  31. How to reduce language is finite to language is regular?
  32. Is there any algorithm which takes regular expression as input and finds if the regular language which expression describes is infinite?

  33. Is unary language with polynomial power context sensitive?
  34. PDA for concatenated languages
  35. Pushdown automata for $\{a^m b^n c^{mn} | m,n\geq1\}$
  36. Wrong DFA from NFA. String Does not contains 110

  37. Meaning of # in descriptions of languages
  38. Use the pumping lemma to prove that {www} is not context-free
  39. Designing a Grammar for $L(G) = \{α ∈ T^* \ | \ |α|\ ≡\ 5\ mod\ 7 \}$

  40. How to prove that a transformed language is regular using an NFA

  41. Can three regular languages be concatenated?

  42. Designing a DFA that accepts strings such that nth character from last satisfies condition
  43. Closure properties of linear context-free languages
  44. How to prove a language is regular?

  45. Closure under swap operator

  46. Using Myhill-Nerode to prove a language is non-regular

  47. Regular Expression Building
  48. Basic doubt in converting PDA to DPDA
  49. Proving $L = \{ w : w \neq w^R \}$ over $\Sigma = \{0,1\}$ is CFL

  50. Grammar/Chomsky-Type for $L = \{ww \mid w \in \{a,b\}^*\}$

  51. Shortest Path using at most k colors

  52. Evaluation semantics: reduction rule for a split statement

  53. Unambiguous grammar for regular expressions
  54. Does this proof work for infinite regular languages

  55. Lambda calculus as the language of universal logic - connectives vs functions in lambda calculus?

  56. Prove that $\{1^m+1^n = 1^{m+n}\}$ is not regular using Myhill–Nerode

  57. What parts of a programming language can't be defined using Regular Expressions?
  58. Proving that $L = \{ a^{n!} \ | \ n \geq 0 \}$ is not regular

  59. It is possible to write any program (i.e. Turing complete) with just one single expression?

  60. Choose a specific regular language to prove a language is not regular

  61. Set of infinite DFA's

  62. Turing machine halting in at least 100 steps on all inputs

  63. Does every undecidable problem contain a decidable subset?
  64. Are regular languages closed under inverse homomorphism?
  65. Confused b/w non-deterministic finite state automata vs finite state automata

  66. Can a DPDA decide if two letters appear the same number of times mod 5?

  67. Does the language of TM's that repeat a configuration infinite times semi-decidable or not?

  68. Can you give me an example word that is in the language $L = \{w | w ∈ \{a,b\}^∗ ∧ |w|_a = |w|_b\} $

  69. Is an inverse homomorphism always a homomorphism?

  70. Refuting $H(L_1 \cap L_2) = H(L_1) \cap H(L_2)$ for homomorphisms

  71. Not able to prove non regularity using pumping lemma

  72. Decidability of intersection of two languages of same type
  73. How to prove that a language created from a context-free gramar's left side is regular(or left-linear)?
  74. Is the language $L = \{a^pb^q \ | \ p \ge 1, \ q \ge 1, \ p \ge q^2 \ or \ q \ge p^2\}$ context free?
  75. Which language is produced by this grammar?
  76. Recursive definition of a language $ L $ over $ \{a,b\} $
  77. Is square numbers written in binary a regular language?

  78. turing machine for the language L ={w#w' where w<w'}

  79. Why does a Turing Machine need at least two states?

  80. P reduction between np-complete to np-complete

  81. Grammer Class/Production Rules of Programming Languages
  82. Explaining why a grammar is not LL(1)

  83. Is the language given by a context-free grammar always context-free?

  84. Context-sensitive grammar for language $L = \left\{ww \mid w \in \left\{a,b\right\}^* \right\}$

  85. Is there an analog of "regular" for infinite strings?

  86. Is there any difference between these two languages?
  87. DFA accepting strings with at least three occurrences of three consecutive 1's
  88. Show that this language is not regular by Pumping Lemma

  89. Is the complement of every non Turing recognizable language a Turing recognizable language?

  90. Is there any language for which $\overline{L^*}=\big(\overline L\big)^*$?

  91. What is the difference between language hierarchy and Grammar hierarchy for LL and LR?

  92. Reduction from L to Htm

  93. How to compare the efficiency of two encoding schemes or hypothesis languages?
  94. Finding language family of given language
  95. What are applications of the levels of the Chomsky hierarchy?

  96. Reduction function from A to its complement

  97. Is a Turing machine without the ability to write on blank cells less powerful than standard Turing?

  98. Systematic approach or algorithm for designing a pushdown automata that accepts a langauge

  99. Intersection of languages using closure properties

  100. Is the set of TMs whose language reduces to a fixed CFL also CFL?