formal-languages

  1. Use the pumping lemma to show the language is not regular

  2. Is square numbers written in binary a regular language?

  3. How do I develop a structured work method for theoretical computer science?
  4. Given are $4$ languages. What kind of language are they (regular, context free, context sensitive..)?

  5. Is language equality for linear context-free grammars decidable?

  6. Does closure under union and concatenation imply closure under Kleene star?
  7. How do you get a regex from this DFA?
  8. Recursive definition of a language $ L $ over $ \{a,b\} $
  9. The difference between absurd reasoning and contraposal reasoning

  10. How can i prove this language is not context free?

  11. How to define a language for an independent set problem of a graph?

  12. Prove or disprove: Complement of language $L=\left\{baba^2ba^3b...ba^{n-1}ba^nb \, | \, n \geq 1\right\}$ is context-free

  13. Finding whether the language is CFL or regular

  14. Set of all countably infinite strings over a finite alphabet >1
  15. Reduction from $3SAT$ to $PARTITION$
  16. Understanding definitions of Deterministic Context Free Grammar and Deterministic Pushdown Automaata

  17. How to prove the well-Definedness of the Operation $.\:$?

  18. How to prove or disprove the well-Definedness of the Operation $.\:$?

  19. Pumping lemma with multiple of prime number + a constant

  20. How can the intersection of CFLs and REGs be CFL if REG is a proper subset of CFL?

  21. Empty words in regular languages
  22. What does $|w|$ mean in the statement " $|w|$ where $w \in L \subset \Sigma^*$"?

  23. Unambiguous grammar for regular expressions

  24. Are there descriptive examples of the architecture of standard content management systems, that provide full user rights handling?

  25. DFA accepting strings with at least three occurrences of three consecutive 1's
  26. Is there a grammar (not necessarily context-free) that generates $n^2$ zeroes?

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

  28. Find any kind of grammar for the language
  29. Closure of context-free languages under "removal of a regular language from the right"
  30. Construct an equivalent NFA for the given regular grammar

  31. Is this language $LL(1)$ parseable?
  32. Language Accepted by a Turing Machine with a Useless State?

  33. How was Idris' `rewrite` implemented?
  34. Is unary language with polynomial power context sensitive?

  35. How to compare the efficiency of two encoding schemes or hypothesis languages?
  36. What is the relationship between problems and languages?

  37. If $L$ is recursively enumerable (or recursive) then so is $L′$

  38. Language of CFG: $S \to aS | aSbS | \varepsilon$

  39. Use the pumping lemma to prove that {www} is not context-free
  40. Is there a regular grammar for the language $\{ w : |w|_0 = |w|_1 \}$?

  41. How can you define the notion of "state" using only a type theory language?
  42. Short quiz about Myhill-Nerode theorem

  43. The importance of normal forms like Chomsky normal form for CFGs
  44. If $L$ is recursive then so is $L^*$, and vice versa

  45. How can I find the center character of a two-tape Turing Machine in n transitions?

  46. Removing epsilon transition from the grammar. What's the difference between accepting languages?

  47. Prove grammars with long derivations generate infinite languages
  48. Give an example of a language whose Myhill-Nerode equivalence relation is such that if $x,y \in \{0,1\}^*$ with $x \neq y$, then $[x] \neq [y]$

  49. Equivalence classes of regular languages

  50. Why is $L= \{ 0^n 1^n | n \geq 1 \}$ not regular language?

  51. Are empty-set languages recursively enumerable?
  52. Sets whose decimal expansions form a regular language
  53. Grammar types constraint after adding a couple of types (and a statement involving them) to a "typeless" language

  54. Context-free Language - Pumping Lemma or Push-down

  55. Is the language in the description context free?

  56. Regular expression for even/odd string on alphabet

  57. Are URI's a regular language?

  58. CFG grammar with fixed number of "distinguished" terminals

  59. Is the language of words containing equal number of 001 and 100 regular?
  60. What is the minimal pumping length of this string $(01)^*$

  61. Show that kleene plus language is a regular language by describing how you build a DFA or NFA for it

  62. Number of words in $L$ of length $n$?
  63. What kind of languages can be recognized by a restricted one-tape deterministic Turing Machine?
  64. How to show that a language is strictly context sensitive

  65. What is the transitive and reflective closure of the derivation relationship?

  66. Converting CFG to CNF

  67. Show that the "first half" language is regular by describing how you build a DFA or NFA for it

  68. DFA or NFA Construction

  69. Why don't we use $ as end marker for input in PDA?
  70. How do you translate these 2 regular languages in words correctly?

  71. Meaning of $|w| ≡ 2 \mod 3$

  72. What's the language of the NFA?
  73. Non-deterministic Turing Machine recognizing a context-free Language
  74. Is the problem of deciding whether a Context free grammar generates exactly K strings is decidable?

  75. Fundamental algorithms in formal language-automata theory

  76. Does rice theorem applies to languages only or does it apply to machines as well?
  77. When is the empty word part of A+?
  78. When is the empty word part of $A^+$?

  79. Let $L_1$ be a DCFL and $L_2$ be recursive language. Is $L_1 \cap L_2$ a DCFL?

  80. NFA: If alphabet {0,1} is given, are you allowed to build a NFA with only 0?
  81. Physical significance of pumping length in pumping lemma

  82. Are the regular languages closed against injecting single letters?

  83. $m/p$-equivalence holds after union with an arbitrary finite language
  84. Pumping lemma for context-free languages - Am I doing it right?

  85. Prove that $L_1 = \{\, 0^m 1^k 2^n \,\vert\, \lvert m - n \rvert = k \,\}$ is not regular using Pumping lemma

  86. Does this grammar generate regular language?

  87. Proving union of 2 regular languages is regular

  88. Grammar for ${a^n b^n c^{n+m}}$
  89. Can a linear bounded automata accept empty string?
  90. If L1 ⊆ L2 and L2 is regular, then L2 − L1 is regular

  91. Create DFA with String of {a,b}

  92. proving {$a^ib^jc^k : j = i \lor j = k$} is not regular
  93. Proving that no two state DFA accept the language L = {$0^i : \forall i \ge 0$} $\lor$ {$^i : \forall i \ge 0$}

  94. Are linear languages always unambiguous?

  95. Concatenation of $a^p$ and $a^m$ where $p$ and $m$ are primes, is irregular?
  96. How do you prove that the set of decimal representation of the 4 divisble natural numbers is regular?

  97. Prove or disprove that the following language is context-free

  98. Show that $L = \{1^n w 1^n | n > 0 \text{ and } w ∈ \{0,1\}^*\}$ is regular

  99. Regular language such that L(r) = L(r₁) L(r) ∪ L(r₂)

  100. Classes of languages for which the language $\{a_1^n \cdots a_k^n \mid n \geq 0\}$ is in the language for $k$ but not $k+1$