1
$\begingroup$

My friends and I are taking a formal languages class and for one of our homework questions we have to prove if these languages are regular:

1) L = {apaqi : p and q are fixed integer values, i >= 0}

2) L = {apbq : p and q are fixed integer values}

For (1), we know it is regular because we can make a DFA out of it, but what we are not sure how exactly the DFA should look like. Should it not be consist only of one state, say q0, and it acts as both the initial and final state, with a loop of "a" moves going through it? Our line of thought is because p and q could be any integers, so whatever p and q would be, we would always end up with a certain number of a's, but we are not sure we are 100% correct.

For number (2), we say it is not regular because p and q could be infinite, thus making the language automatically irregular.

We are still quite confused on which concepts are correct. This is still a very abstract concept for all of us and any guidance would be appreciated. Thank you!

$\endgroup$
  • 3
    $\begingroup$ $p$ and $q$ are fixed integer values, which means that you choose their value once and then generate all the strings that match the given pattern. Also, since $p$ and $q$ are integers, they cannot be infinite. $\endgroup$ – David Richerby Mar 3 '16 at 4:57
  • $\begingroup$ Hint: You can use something called the Pumping Lemma to disprove those that you feel are not regular via contradiction. $\endgroup$ – Banach Tarski Mar 3 '16 at 6:46
  • 3
    $\begingroup$ 1) "we know ... we can ... we are not sure" -- contradiction. 2) Hint: construct an automaton for $ab^i$. 3) "p and q could be infinite" -- nope. And don't change your interpretation of notation from one task to the next! 4) See here and many questions with tags like yours. $\endgroup$ – Raphael Mar 3 '16 at 7:45
  • 1
    $\begingroup$ I do not see a question here. Community votes, please: is this unclear? Or a duplicate of our reference question? $\endgroup$ – Raphael Mar 3 '16 at 7:45
  • $\begingroup$ Please ask only one question per question (don't ask about two languages/exercises in the same post). Also, we discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$ – D.W. Mar 4 '16 at 0:39
1
$\begingroup$

Think of it this way. Fix $p$ and $q$ arbitrarily – for example, take $p = 4$ and $q = 5$. Then $$ \begin{align*} L_1 &= \{ a^4 b^{5i} : i \geq 0 \}, \\ L_2 &= \{ a^4 b^5 \}. \end{align*} $$ Now try to answer your question. The answer will be the same no matter what values you choose for $p$ and $q$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.