Let L = {0^(n) 1^(n+6) | n is a positive integer} is L regular? I am trying to u

Question

Let L = {0^(n) 1^(n+6) | n is a positive integer}
is L regular? I am trying to use pumping lemma for this, but I am not sure how to do it...

Also, how do I show that this language is a context free language??
please help me

Explanation / Answer

You can prove this is a context free language in 2 ways: 1. By constructing a context-free grammar: A -> 0B1111111 B -> 0B1 | epsilon where the start symbol is A 2. By constructing a pushdown automata (PDA): Step 1: Push 0's into stack Step 2: After the first 1 comes, start popping a 0 for each 1 Step 3: After the stack is empty, accept 6 more 1's Step 4: If the string is now empty, accept. (in all other cases reject)

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.